mail server: removal from spam database

check with

http://www.robtex.com

black list checker

use dnsstuff then follow delisting links
http://www.dnsstuff.com/

http://www.mxtoolbox.com/blacklists.aspx

http://www.au.sorbs.net/lookup.shtml

http://www.spamhaus.org/lookup.lasso

http://www.barracudanetworks.com/reputation/?pr=x.x.x.x