This has happened before and some mail servers will tell you that your IP has been blacklisted (RBL, CBL, etc) but I can't find that site to check anymore and searches result in a site that may or may not be legitimate.
DNSstuff also has a subscription based service called RBLalerts that will monitor 130+ blacklists for an IP address you specify and notify you if it has been listed or delisted. I haven't tried this service, but it might be worth a try if this issue is impacting your organization.
Although if an ISP is blocking you purely on RBL check then they need educating. You should never block purely on this as it can lead to a lot of false positives.
You should also check for yourself at rfc-ignorant.org. Being in their zones isn't being blacklisted, more like graylisted, but it doesn't help you any.
www.dnsstuff.com is paid for but it does a lot more besides checking for blacklisting, which indeed it does.
GENERALLY SPEAKING, it is fruitless to regularly check this. There are too many blacklists and they come and go. False positives are rare, and they can usually be dealt with quickly when they happen. Make sure users know to contact you if mail is not getting delivered, and then deal with it when it happens.
The administrator of the domain actually doing the blocking can usually tell you the fastest way to get unblocked, or can add you to a white list for their domain. You also may be able to tell from one of the notes or headers on a returned (blocked) message.
Additionally, you need to do the basic things to minimize getting blocked in the first place. This includes making sure you don't have relay enabled and disabling outbound SMTP from other than your mail server.
Finally, you should make sure that your users aren't sending spam! A couple of PCs infected with an "email the address book" worm can be enough to trigger a blacklist. Keep A/V running and up to date, including inbound and outbound mail and web browsing.
Spamlab is another site with over 30 RBL. It's also relatively easy to remove your site from the RBL through www.spamlab.com
I use the rblcheck program.
You can check if your IP is listed on over 30 blacklists at http://www.viewdns.info
Nice fast site with clean output! Best of all its FREE!
GENERALLY SPEAKING, it is fruitless to regularly check this. There are too many blacklists and they come and go. False positives are common, and you'll never keep up with trying to deal with them when they happen. Make sure recipients know to contact their own provider if mail is not being received, and then deal with it when it happens.
The administrators of the domain doing the blocking are responsible for providing spam protection service for their users. The extent to which they do a good or bad job (false positives, false negatives, etc.) is beyond your control.
Although this is pretty much the opposite of what tomjedrz said, I agree with his "soapox" comment in its entirety.