IP address is listed on spamrl.com

Sometimes it can be the anti-spam solution on the sender side, where the only solution is to add the recipient's domain in the white list and hoping this works because some SPAM solutions still block it ( do this only after making/being sure their network/server is indeed secure, naturally). Might also be that your client's provider's ip-range is in blacklist, where they intermittently end up because they have a lot of spammers on their range, good luck solving that one, just speaking of experience :)

But if they show up just one time as being blocked on the entire list, it's enough to cause trouble ... So either there is something wrong on their network/server or it's the ISP or it's the local (sender's) SPAM solution...

The issue is that your client is using the list to filter out emails  classified as "spam".  In the case your server is the one listed on the uce-dnsbl1.rbl.spamrl.com and not their server.

Double check whether they know they are using this RBL LIST in the first place. in either case there are better more responsive lists.

This list is based on honeypot email addresses and if a "sufficient" number  of emails receive an email from a server, that server could wind up on their list for a time.

In this case, your server seems to have wound up on the list.

See http://mxtoolbox.com/blacklists.aspx and you might want to persuade your client to use other lists.

If the user has a Firewall that handles SMTP proxying and that is where the RBL list is being used, checking the log to see whether outgoing emails are being blocked by the RBL test and/or reviewing the configuration on whether the outgoing SMTP should be subjected to the RBL list after confirming and making sure that the internal Mail server is not an open relay.

Neither his domain  nor my domain show up as blacklisted at http://mxtoolbox.com/blacklists.aspx.  Plus, the IP address cited in the returned email is different from the ones that either his domain or mine resolve to, according to that same mxtoolbox website.  Is there a way to know to whom this cited IP address belongs?

I wound up at uceprotect.net which showed that the IP address cited in the bounceback belongs to Network Solutions.  So I called them, and a very nice lady confirmed the subnet to be one of theirs and promised to get their engineers on it.  Thanks, Arnold!  I'll report here what I hear back from N.S.