RFC 1123 - Load balancing question

[Jon Doe]

Can someone please help me in understanding the information contained in the 
following section of RFC 1123?
I'm currently involved in a situation where the other company I'm dealing is 
quoting RFC1123 with claims that my mailer is not complying
with this passage and therefore, it's my fault that mail is being delayed in 
reaching them.

RFC 1123

5.3.4  Reliable Mail Transmission

(1)  Multiple MX Records --  If there are
              multiple destinations with the same preference and there
              is no clear reason to favor one (e.g., by address
              preference), then the sender-SMTP SHOULD pick one at
              random to spread the load across multiple mail exchanges
              for a specific organization;


The short story is that, we send over 15,000 messages to one company, and 
during peak times we see delays of those messages to be over 4-hours (I dont 
see delays to any other domain). They have 6 MX records and during these 
peak times, my SMTP logs show attempts to connect, but there's always 
delays. Even when I telnet to port 25, it takes up to 20 seconds to even get 
the banner screen. The other guy says that they show that they most of my 
mail sender's traffic attempting just 2 of the 6 MX records they have, and 
therefore not "spreading the load".

So my question is, how should this passage in the RFC be interpreted? What 
does the RFC mean by "spread the load"? My SMTP sender simply finds the MX 
server, connects and keeps sending to that one server until the TTL expires. 
Also, what does the RFC mean by "random"? When I do an nslokup on my DNS 
server, I get a list of MX records, and it's this list that my mail sender 
uses in determining where to send the mail. By the way, I found a similar 
passage in RFC 2821 section 5.

My thought is, my sender is fine, but I want to be armed with the correct 
information before responding to the claims that my sender isn't RFC 
1123-compliant.

Thanks in advance!