The problem is with Gmail, not with Mail.app and the answer lies in using the advanced IMAP settings from Google Labs.