Since my emails to and from Hotmail in the past 2 weeks regarding the block on my company's main email server, I have since found that it is being blocked by a DNSBL called ivmSIP/24 which seems to operate on a basis that if one IP address sends spam or junk emails they block a huge chunk of IP addresses either side of the offending one.
Many server farms operate with continuous blocks of IP addresses for their servers so if one server sends spam, potentially hundreds of others who have never sent junk before will be blocked and blacklisted by ivmSIP/24.
I have contacted the company who runs this blacklist (http://dnsbl.invaluement.com/) and I am waiting to see if they can remove our server from the block list as our servers IP address as they have it blocked but they do not seem to have any information on when it was listed or why.
Update 19th march 2012.
Had a very fast response from ivmSIP/24 who have confirmed that it wasn’t our mail server which caused the block but due to "other IPs on the same block sending much-unsolicited bulk e-mail in recent weeks. The most recent from this /24 block was sent within the past couple of days"
ivmSIP/24 have manually removed our mail server from their block.
Hotmail/microsoft/msn/live do not use the blacklist from ivmSIP/24 but operate similar systems so their block of our mail server is not due to our own mail server but blocked due to other servers at the same host (Rapidswitch) which are sending spam.