I'm writing this up mainly because it took a long time for me to figure out what the problem was and phoning the good folks at Shaw technical support yielded no assistance.
The Summary
Having problems sending email to Shaw or other ISPs? In addition to black lists and the like, check your reverse DNS it may be too "generic".
The Problem
Mail sent from my mail server to Shaw's (ie anyone@shaw.ca) would sit in my outgoing queue for a long time, some times over 24 hours. 95% of the time it would eventually be delivered, however 5% of the time it would bounce after sitting in my outgoing queue for too long.
The error message being reported by the Shaw mail server was "550 Too many invalid recipients". This would happen even if there was only a single recipient and the address was known to be good. Clearly the description was not accurate.
Some Background
I host my own email on a postfix server I run at home. I pay for a static IP address and the IP is not listed in any blacklists.
Several months ago I switched ISPs and at about the same time I noticed that email to @shaw.ca addresses would sit in my outbound queue for a long time before being delivered. Calls to both my ISP and Shaw proved less than useful. Having been a Shaw customer at one point, and having used their email servers, I put this down to being a mail server issue at their end.
Yesterday I sent an email to someone via Craigslist and the message bounced. Unlike Shaw's error message the message from Craigslist described the problem and pointed to http://www.craigslist.org/about/help/generic_DNS which defines "Generic DNS as":
A hostname that contains:
The Sollution
The reverse DNS entry for my IP address managed to trigger two of the "generic DNS" issues, it included both my IP and "dsl".
I phoned my ISP and asked to have the IP reverse to the hostname of my mail server. Once the DNS had updated the problem was solved.