Have you eliminated/removed syncing options with gmail?
I have not used that service, so I am not sure where that genie might be hiding.
Check Preferences for both Mail/iCal to eliminate the gmail address.
Check System Preferences iCloud/Mail, Contacts & Calendars for references to gmail.
My husband doesn't use gmail at all so I don't think that is it. I use gmail but that shouldn't affect his calendar/mail, right? So frustrating! But thanks for cluing me in on how to get rid of the "previous recipients" cause that helped me both on his computer and mine. If you think of anything else I can try, that would be awesome.