Well over a week later and we finally seem to have basically resolved the problem.
The biggest thing preventing progress was the fact that their deliverability problem reporting forms, and junk mail reporting program application forms, went offline for a week.
The second biggest problem is that the people responding to the deliverability problem forms were not helpful - a management policy as far as I can tell, not a failing on the part of the representitive in question - insisting on pointing me to a page full of policy guidlines rather than telling me what was actually wrong, depite polite requests from me for them to simply tell me what the issue was.
The bottom line is that if you get blocked, do the following before you continue:
1) Sign up for the JMRP (Junk Mail Reporting Program) - this is similar to AOL's feedback loop.
WARNING: If your IPs are not delagated to you at ARIN/RIPE/Whatever, your application will be refused, but with a polite note to say all they need is for your ISP (e.g. co-lo provider) to contact them to state that you have the sole sending rights on those IPs. Once your ISP does so, you should be OK (this was how it worked for me)
2) Sign up for the SNDS (Sender Network Data Services) facility. This basically gives you an indication of the type of traffic your IPs are sending to Hotmail/MSN/Live.com addresses, who that traffic is from, how many people it was sent to, and whether Hotmail considered it to be spam or not.
WARNING: You will almost certainly not be able to request that your entire subnet be added to your account unless there is a contact email address associated with your subnet, and that contact address belongs to you. However, you should be able to add individual IPs as long as the rdns points to a domain in your control (basically it looks up the rdns, then offers to send a confirmation email to abuse@ or postmaster@ which contains a link that has to be clicked on to activate that IP)
WARNING 2: This is the really annoying thing. You may look at your historical SNDS data, and see nothing but "green" (i.e. no junk mail) for months on end, up to the point your IPs were blocked. This will get you wondering WHY your IPs were blocked in the first place. Unfortunately - again for management policy reasons - the hotmail support people won't explain why this apparently odd situation has come about.
3) NOW you can fill in the hotmail deliverability problem report form. Be as thorough as you can.
NOTE: The form is really geared towards mass mailers rather than hosters/vps providers. You just have to fill the forms in as best you can, with a "not applicable" or ten as required.
Assuming the person who attends to your form isn't in a bad mood, and assuming you have satisfied them you are not an evil junk mailer, the block should be lifted quite quickly after you get a response from them.
I did not feel confident that they would take any notice of what I was trying to tell them, and was worried that I'd have to try snail-mailing in order to get the attention of a "supervisor" if I didn't get unblocked. Again, a very big company has the power to crush a small one at its whim, with no explanation and no way for the small company to seek redress. I can't tell you how relieved I was for the block to have been removed, but I'm not confident that it will stay unblocked.
NOTE 2: I have not received a single message via the JMRP - this worries and confuses me. I had expected a flood of stuff, allowing me to maybe find a customer who had been forwarding email from their hosting account to a hotmail account and who was being spammed to high heaven. But nothing. Not one message. In a way this is not unexpected -- I was not seeing anything in the logs to indicate such a thing was going on. But it again means the reason our IPs -- our entire subnet -- was blocked remains a total mystery.
If you want to rent a UK-based VPS that comes with friendly advice and support from a fellow ART fan, please get in touch.