It has been over one year since the question was posted, and recent posts show the problem still occurs. I want to add my voice.
This is one area Macs use to run circles around PCs. While my colleagues were always struggling to get their PC to talk to a projector (and set the resolution correctly), I connected my PBG3, PBG4 and MBP 2.4GHz (this one using a DVI-to-VGA adaptor) to any projector and it always worked. Sometimes I could further improve on the resolution and refresh rate that were selected automatically, but the initial setup was always decent. Sometimes I needed to click "detect monitors", but not always. I usually needed take no precaution. It was very rare that I had to put to sleep, connect, and wake the Mac. By the way, I always used extended desktop to be able to benefit from the presenter's screen offered by Keynote. To me, mirroring the screens has been an inferior solution.
I still connected without problem at a recent conference (after upgrading to Snow Leopard), but most projectors at my workplace give me difficulties now, even though I connected to the same projectors without a hiccup a few months before.
Usually the projector says "no signal" and it does not matter if I connect before or after turning the projector on (something I never even worried about before).
The last time I needed to connect to a projector at my work (Jan. 7 2010, the only way I could get it to work was to select mirroring with a resolution of 1024x768 at 60 or 70 Hz first, and then "detect monitors". Disabling mirroring, changing resolution, chosing higher frequencies or "detecting monitors" too early resulted in a "Signal not compatible" or a "no signal" message.
This is really annoying. As others have noted, it makes me look unprofessional. Often I was able to use my Mac at conferences that did not allow computer switching between talks because I promised I could switch computers very quickly. I can't dare make this promise anymore. I'll have to save my presentations to pdf and use a PC, losing some of the benefits from Keynote.
I notice that many of the posts here were made before Snow Leopard, but it is only recently I started having problems connecting to some projectors and I wondered if Snow Leopard was responsible. I am less certain since reading this thread, but then why is it that only recently I have been encountering difficulties connecting to projectors? I was about to say that my hardware has not changed, but the motherboard was changed in the summer under Apple Care, so strictly speaking my hardware did change.
Someone mentioned "bad cable" as a possible cause, so I'll try a second DVI-to-VGA adaptor soon and will report back.
Denis