No, your ISP is not blocking 25, or you would not be able to telnet to port 25.
What I have found is that this issue is frequently related to errors in DNS. Some ISP's (the list is growing) will do different types of verification to check if a message is valid before receiving it. I am sure we are all familiar with the lack of a reverse lookup for a mail server, but some ISP's are also checking to see if an email account is valid before receiving the message.
This validation is done by looking up the MX record for a given domain and then checking the mail server listed in the MX record to verify that the sender has an account on that machine. Most mail servers will respond to this query. Once it is known that the user does exist in the mail domain, the mail is received and delivered to the appropriate box.
If the server does not respond to this query or the senders account does not exist on the server referenced in the DNS MX record for that domain, the 554 DNR error message is issued.
Check your MX Records and your PTR records on your DNS server. If you have more than one MX record for domain make sure the records are valid and the priorities are properly set. This will fix a lot of the 554 problems.