You may have encountered this page by accident, or I may have pointed you at this page because you've asked me why mail from your system is not being accepted by my mail servers. This page documents one specific reason for my mail servers being unreasonable, the reasons, and references to supporting documentation.
The raw fact is that servers that announce themselves when conducting SMTP transactions with "HELO some_name" or "EHLO some_name.some.domain" are in breach of mail standards. As the problem of spammers increases, many more mail servers are refusing to accept mail from mail servers that do not stick to the standards.
It is quite possible if you ask nicely that I'll put your mail server into an exceptions list so I can allow mail delivery from your mail server. But that does not solve your problem ... others will continue to refuse mail from you, and may not be as willing to co-operate in fixing your problem.
And it is your problem. Your mail server is in breach of the relevant standards for mail, and anyone is perfectly free (and being quite reasonable) in refusing to accept mail from a non-complient mail server. If the relevant mail administrators were being unreasonable, they would report you to your ISP (not that your ISP would do anything).
The Internet operates on co-operation ... you agree to run a mail server to a set of standards, and I'll agree to accept mail onto my private mail servers. Without co-operation and standards, the Internet will collapse into the multi-network world of the 1980s and early 1990s ... and let me assure you, it was painful.
Now some details of your "sin" :-
The standard that governs the basic transaction language for delivering mail to remote mail servers is RFC2821 (which updates with minor changes RFC821 which dates to 1982 but in turn replaces some earlier standards). In this, a mail server is required to send either a "EHLO" command or an "HELO" command (which both essentially amount to the same thing).
The parameter to this command is required to be a "domain" which in this case is either an "address literal" (essentially an IP address in square brackets), or a fully qualified domain name. The host name part of the domain (the bit before the first dot ... if any) must only contain letters, digits, and the hyphen ('-').
Mail servers are REQUIRED by RFC2821 to reject service to mail servers that supply a non-standard hostname. The relevant part of the RFC states :-
In particular, the underscore character is not permitted. SMTP servers that receive a command in which invalid character codes have been employed, and for which there are no other reasons for rejection, MUST reject that command with a 501 response.
Now you can argue that this is unreasonable, pedantic, childish, or anything else. Does not really matter. It is the standard, and if you want to exchange mail with other standard mail servers you have to follow that standard.
I don't know the details of your mail server, so I can't give you specific instructions. Judging by previous experience it is most likely that you are using Microsoft NT/Windows 2000/XP and Microsoft Exchange. Even assuming that I'm right, I still can't help you too specifically ... no self-respecting long-term mail administrator is going to admit to knowing too much about Exchange (yes that is a hint).
If this is the case, and the name of your server was configured as something similar to "FIN SERVER" (i.e. with a space in), you need to reconfigure the name of your server. Microsoft apparently recognises that spaces are not permitted, and "helpfully" changes the spaces to underscores. So you don't configure your server with underscores but they are there anyway!
Note that I am unaware of the consequences of renaming a server.
Ah yes! It would not surprise me if it did.
Originally mail servers were intended to be very permissive in what they accepted and what amounts to a relatively small mistake in the protocol (supplying a hostname with an illegal character) would have been regarded as trivial. Unfortunately, the Internet is no longer such a tolerant place as regards mail, because of the activities of spammers.
More and more mail servers are becoming more and more restrictive in what they accept. Some are even checking that what is given after the HELO command can be looked up in the DNS, what is returned can be looked up in the DNS, and what address the network connection is coming from matches that HELO domain.
In addition, there has been some confusion over whether the RFC's permit or deny the use of underscores in domain names. Part of the confusion is due to the fact that underscores are allowed in DNS names, but underscores are not permitted in Internet domain names. Is that confusing ? Well others also found it confusing.