I can't stand these pseudo solutions (RazzMaTazz) where when you ask for cross platform synch, and the answer is just 'just use the Megasoft shit stuff" as you suggest by opening a Microsoft/Hotmail account!
I just got today a new HTC Desire/Android and getting the same problem, but exactly as i got with my previous HTC Win 6 too!
The simple reason is over proprietary solution, even against old same brand products!
The function activates only with selected Windows products ...
So, some possible solutions:
1-Switch to full Gmail but web and not mail client, and proprietary too ...
2-Auto forward your usual mail to your Gmail account and back to 1
3-Look for a 3rd party intelligent tool that will do the job as i have previously bought.
So i will first look for a net mail client that support Gmail contacts and any other mail. If not any, then will look for a 3rd party tool.