I had the same situation. I only use Outlook contacts and initially every single email I ever emailed from my gmail was dumped on my phone along with Facebook contacts. There's a utility in the market called something like contact remover that allows you to mass delete contacts. I nuked all my contacts, disabled gmail contact syncing and Facebook contact syncing, and only allow Exchange. This did the trick for me.
Sometimes it will not allow you to remove your default gmail account so you have to do this. Good luck.