Now, some vendors are beginning to block mail coming from Gmail. Issues from mails being extremely delayed to mail simply not coming through at all have been reported. Due to the number of relays Google operates, not all of them are blocked or filtered – so sometimes mail gets through, other times it doesn't. The primary source of the blocking seems to be MessageLabs, Antigen and a few other anti-spam companies.
They, of course, point the finger at Gmail, and tell Google that they need to fix their CAPTCHA. You'd think with the tremendous amount of capital and resources that Google has, this would be no problem for them. In the meantime, this can't help people put faith into Gmail as a reliable mail service.