First step should be to contact the support ninjas via email to
omnifocus@omnigroup.com or call 1-800-315-OMNI during US West Coast business hours. Omni's got one of the best customer service departments around, and it doesn't cost you anything to get their help. They can help you get your database back in sync, and it shouldn't be necessary to lose any data.
Syncing through MobileMe most certainly does work (I do it dozens of times a week), although it can be slow at times. Part of the reason it is slower on the iPhone is that the processor on the iPhone is much slower, and there's a lot of work to be done. There's also a bug in the shipping version that causes some of that work to be done in an inefficient fashion, with a fix being tested internally at Omni right now.