I'll admit from the off that I'm slow on the uptake with this one, but having tried out the NuevaSync for the first time at the weekend I'd not be doing my job properly if I didn't point you in the way of this wonderful service...
In the company's own words it "allows direct, over-the-air, native synchronization of certain smart phones and PDA devices with public PIM, and calendaring services including Google Calendar. NuevaSync does not need any software installed on your device because it uses synchronization protocols that are already built in."
Plaxo contact support is in there too and one other thing: it's all free!
Now while support platforms like Windows Mobile have this sort of thing already, the big news is really what it can do for iPhone/iPhone 3G and iPod touch owners. It supports multiple colour coded calendars direct from Gmail - something the products are supposedly incapable of doing - and it works brilliantly. On top of this you get MobileMe/Microsoft Exchange-esque functionality with OTA two way syncing between your Gmail contacts and calendar while Tasks and Email are in the pipeline. (Tip: import contacts/calendar from Outlook, to Gmail/Google calendar first! It's a simple process)
Of course you may ask how NuevaSync plans to monetise such a useful service and for the meantime the simple answer is it doesn't. Speaking to NuevaSync representative David Boreham he explained that a premium paid service is planned "to cover the cost of running the service" but that it isn't imminent.
NuevaSync provides idiot-proof instructions and setup walkthroughs if you fancy giving it a try. After a weekend of testing it has allowed me to give up Outlook completely and, in Gordon World, that's about as big a compliment as I can give...