[jiggy2011]

I had a similar problem and never found out exactly why it happened.

The hypothesis I came to was that we weren't using SPF records on the domain associated with our IP address for a long time.

Some spammers were taking advantage of this by sending emails from different IP ranges with the From: header spoofed to be from our domain.

So Spamhaus blocked our IP address on the grounds that spam filters would also be able to confidently block anything appearing to originate from a domain name that resolved to our IP address.

[jackalope]

It's extremely unlikely that spoofed headers or the lack of an SPF record would get you listed on an RBL, especially Spamhaus. I can't guess what happened in your case, but somehow your IP address obtained a bad reputation or was unlucky enough to be in a tainted block. FWIW, the very first thing I do after getting an IP allocation is run an RBL check on it and demand a replacement if it's listed anywhere.

[jiggy2011]

Yes, it was a fairly weak hypothesis. OTOH we got on several RBLs a number of times and managed to get taken off them. Once I added an SPF record it hasn't been a problem since.

Didn't use SPF to begin with because there was a large number of hosts legitimately sending mail for the domain and it was a pain to get all of the IP numbers for various crazy reasons.