I just reset my mobile, deleted the device in the Mobility webadmin and restarted synchronizing. Contacts & Calendar are ok (Calendar just the same incomplete, but that is a different story), but Email was wired. Settings:
- Sync all 30 mins
- 1 Month time
- Device: Motorola Milestone, Android 2.1

The effect:
- All still present emails were synced -> OK
- All deleted Mails (but not purged in GW account) were synchronized and show up as unread -> NOT OK

IMHO deleted mails should not be synchronized to the device again after resetting the sync.

Hope that gets fixed...