Here's what I did to get mine to work (I have a feeling it was more luck than actual steps) but here it goes:
1. I turned off my Exchange Account contact syncing and had all the contacts erased off the iPhone.
2. I then sync'd my MobileMe Contacts to my phone (which are just a copy of my Exchange contacts) and began to start testing MobileMe to see if contacts/calendar events would sync both ways...they did.
3. I then opened up Outlook and made sure ALL of my folders were updated. I went through and deleted contacts that no longer were of use to me. Outlook sync'd all the folders and I left it open.
4. Now I turned off my MobileMe contacts/calendar sync and deleted all the information from my iPhone, so I had absolutely zero contacts and calendar appointments on my iPhone.
5. Next I turned back on my Exchange contacts/calendar sync and as usual the contacts and calendar all sync'd back fine.
6. Now I tested things out. First I made a "test" contact on my iPhone, it sync'd properly with Outlook, I then deleted that contact on my iPhone, it sync'd again fine with Outlook.
7. Next I made a "test" contact in Outlook and had it sync with the iPhone and it did so properly. I then deleted that contact in Outlook and it was removed from my iPhone like it should have been.
8. Now I just have my Exchange account set to sync my Mail, Calendar, & Contacts, and everything is working fine. For MobileMe I just have Mail and Notes syncing.
I highly doubt this guide will help anyone but it worked for me so maybe it will work with people who are experiencing issues with Exchange. I personally believe the key is leaving Outlook open the whole time and let it fully sync, I would go days, even weeks without opening Outlook and I think that had something to do with the syncing issue. Now I will be sure to have Outlook open most all day, or open it throughout the day often.
I am using Microsoft Office 2010 Professional Plus, which includes Outlook 2010, just so people know what I was using.
Hope this may help some people, I'm going on about 40 hours of no sleep so excuse me if there are typos or things not really explained well, I am going to try and sleep so if you have any questions for me just ask them in the thread and I will respond as soon as I can.
Patience is also needed, I've timed how long it's taken for some of my syncs and it ranges from anywhere from Instantly to 3-5 minutes before things sync. So don't give up quick, allow the servers to do their things.
Later people!