I have had the same problem on several occaisions.
SORBS (
www.sorbs.net ) maintains a database of known blacklisted IP addresses and servers in an attempt to lower spam and so on.
Some commerical servers (certainly not all) utilise the service SORBS provide.
When one of these servers recieves a messeage it first queries SORBS to determine if it is blacklisted or if it is dynamic.
If one of these conditions is true it will reject your message.
If you believe you should have a static IP address, it is possible that SORBS believes your IP is infact dynamic and not static.
The SORBS website has facilities to check your IP address to determine its status, if it returns saying you have a dynamic (or other) IP address, you can request delisting... You have to go through a whole process, and it will involve some communication with your ISP also.
On numerous occaisions I have attempted a delisting with NO success at all... no even a reply. I also had my ISP attemp, with the same result.
I would recommend that you get on to your ISP and get them to change your IP address to another one... BUT get them to query it against the SORBS database before they assign it.
You will most definently need an IP from another range, because the SORBS databasee appears to maintain these blacklists in IP pools, so just getting an incremented IP address most likely will be useless.
Hope this shed some light on the situation for you.
Cheers!