Note to MessageLabs... a little help?

This post is for any of my MessageLabs readers.  I tried to send an email to my travel company today using my Gmail account (which I pop through Thunderbird).  I got an NDR saying the following:

 

 This is an automatically generated Delivery Status Notification

Delivery to the following recipient failed permanently:

     address_removed@no_address.com

Technical details of permanent failure: 
PERM_FAILURE: SMTP Error (state 12): 553-Message filtered. Please see the FAQs section on spam
553-at https://www.messagelabs.com/support/ for more
553 information. (#5.7.1)
  

I went to that link and I didn't see any FAQ's but I did see a list of bounce messages which I could click on for more information. I clicked on the first link (553-Message filtered) and followed the instructions. 

  1. My connecting IP is not on any blacklists but the IP address does not have a reverse DNS.
  2. I'm pretty sure bullet points II through VIII don't apply to me, though if point III, V or VI are the problem there isn't much I can do about it.  My machine does not have a virus, I can't control the mail server, and believe-you-me there isn't any spam content in the message.

I don't really want to add myself to my travel company's approved client list, I'd just like this to work.  Thanks.