I have 3 locations setup very similar. All are behind Cisco ASA 5505's and have Xerox ColorQube's behind them.
Users are not able to use the scan to email function at 2 of the 3 sites. We're using gmail as our SMTP server.
We've tried replicating the settings from the working location (i.e. username/pw, DNS, etc). The same account can be used on a PC, and that PC can send emails with attachments using the account.
Packet inspection on the ASA shows outbound traffic on port 53 and 587 and also return traffic - the printer has perfectly fine internet access.