IP address blacklists are normally unreliable and a poor approach to controlling whatever it is people are trying to control. But administrators definitely use them.
Talk to the Administrator
The first thing that I would do is ask that forum owner exactly what blacklist it is that he’s using. There are probably hundreds of different blacklists, and that’s part of the problem. There’s no way to know which one he’s using or which one the checking services that you’ve been looking into are actually referencing.
He may be using a private blacklist; he may be using a blacklist that simply isn’t all that popular and therefore not showing up in any of these other services.
If you can get the source of that blacklist, then maybe you can appeal. The problem is that most blacklists are exceptionally poorly managed. In that sense, they are very easy to get on and often, they’re very difficult to get off.
But it’s worth a try.
Changing your IP address
If you can’t get off the blacklist or figure out which blacklist you’re on, you’re pretty much out of luck for the direct connection.
Whether or not you can change your IP address is more a function of your ISP.
Coming at it from a different ISP – such as an internet café – would certainly do that.
If you just want to change your IP address (say from home), the chances are that it’s not just a single IP address that’s blocked but an entire range. If you get a new IP address from your ISP, you may still be within that blocked range.
Use a proxy
An alternative might be to use a proxy service such as The Onion Router (TOR), or a VPN service like Hotspot Shield. They actually have different purposes (anonymity, in the case of TOR and security in the case of VPNs), but in both cases, you will appear as coming from a completely different IP address. It will be a tad slower.
There are free VPNs (Hotspot Shield is one), but you can also pay for VPNs and end up with slightly better performance.
The question you’re probably also asking is how did you get on a blacklist in the first place? Well, there’s no way to really know. Most commonly, it’s possible that you inherited the bad behavior of someone who was assigned that IP address at some point in the past.