I had been conversing with someone via email earlier Tuesday, having no problems. However, my would-be last email of the day was returned by the recipient's mail system. The error message was

"SMTP error from remote mail server after initial connection:
host zzzz.zz.zzz [xxx.xxx.xxx.xxx]: 554-zzzz.zz.zzz
554 Your access to this mail system has been rejected due to the sending MTA's poor reputation. If you believe that this failure is in error, please contact the intended recipient via alternate means."

I got this message sending new emails or replying to hers, even a one word email like "test".

I've checked my mail server's IP vs. Spamhaus and a few other blacklists with no black marks. What can I send to her (via personal email) to have her company's IT people check or look for? Adding my email to a whitelist, or my IP, or is there something I need to verify on my end?

They would need the full header of the rejected mail, they would have to add it to their white list to get through. You (or your isp) have been blacklisted, so anybody using whatever subscription list they are using for domains to block will block you too.

Thanks Mike... I looked and found my IP associated with my ISP have a black mark or 2. Do I contact the ISP about this, the blacklisting source, etc. for help? This could explain why I haven't received a couple of replies (or mebbe they just don't like me...) elsewhere.

You may want a full salutation, letter body and signature in your message. Screening software look for all these things.

Not really all that critical IME and not the issue that the OP is facing. In his case the MTA (Message Transfer Agent) is rejecting the connection based strictly on the IP address of the sending system, not based on the content of the message.

To the OP, if you are using an ISP as your mail relay agent then you'll likely need to get them to contact the blacklisting agency. The hard part may be determining which service has you blacklisted. If the rejection note doesn't include it you may have to go to the IT staff of the intended recipient to figure out what service they are using.

Or, if you are sending directly from your own connection (i.e. email server in your network, not a relay through their server) then you need to get your home/office IP address cleared.

I've checked and a group of Verizon IPs are on Spamhaus and Sorbs.net blacklists (at least). I am guessing that an IP showing somewhere in the header can cause the problem? I've sent a note to Verizon asking to look into this. Don't know what else I can do for now.

Does your mail get delivered directly from your home/office IP to recipients or does it go via a relay? Many balcklist services will flag traffic from DSL/cable modems because of the potential for those systems to be spam-bot infected. It is easier for them to justblock the whole range than to actually identify the bots and the number of legit senders affected is very, very small.

If you are set up that way you should have the home email server relay through the ISP's on-net relay. That server is rarely blocked and they actually care about unblocking it when it happens as it affects all their customers, not just one guy at home.