Calendar Sync with Google Calendar Problem: Deleted Calendar Event still Exist
Have you tried to make sure that the calendar is setup through: http://www.google.com/support/mobile/bin/answer.py?answer=139206

Also, make sure you setup as an exchange server and not a Gmail account.