The OP used the hdmi_safe=1 parameter, which actually sets hdmi_force_hotplug=1, so that did not work. The only reason I know this is that yesterday I came across the exact same problem you mentioned with the "edge of being fine" problem.
On my original pi, Model B Rev 1 running an old version of Soft Float Wheezy, when I started it up sometimes I would not get a HDMI display, but a quick reboot before anything important loaded, and the screen would usually come up fine. I just lived with it.
So I received my Model B Rev2 board yesterday and figured all I had to do would be to image the card with the newer Raspbian and just hook up all my previously running hardware and it would be a quick good to go. Wrong ! ; and rebooting was not helping. So I am thinking, here we go, is it the newer operating system or the updated pi hardware. So, I discovered that after putting it into safe mode the display magically appeared (hdmi_safe=1).
Now safe mode sets a pretty much useless resolution which I fixed, but I had a feeling that there was something else going on. So, the hdmi_safe=1 command sets a specific set of parameters, so I set each command one at a time until I found which single command fixed the problem.
These are the parameters that hdmi_safe=1 sets:
hdmi_force_hotplug=1
config_hdmi_boost=4
hdmi_group=2
hdmi_mode=4
disable_overscan=0
It turns out that hdmi_force_hotplug=1 fixed the problem, and I did not have to mess with any of the other commands above, including hdmi_safe=1. Apparently HDMI on my monitor was on the hairy edge of working with the Rev 1 board, but would not work at all with the Rev 2 board. Assuming that it is a monitor related issue and not a pi related issue, I am including the model of my monitor in the event that others come across the same problem.
Monitor: Samsung T220HD