If you made it into Spamhaus then its pretty much guaranteed you were really sending out spam. Spamhaus are very well respected and have an incredibly low false-positive rate (infact I've seen no false-positives caused by Spamhaus, and that's on various busy mail servers where a Spamhaus data feed subscription is in place). They take their work very seriously and as far as possible they aim manually review anything that's borderline before it gets into their database.
The only exception to that is if you were on the one specific Spamhaus feed that is a list of ISP broadband connections which is used as a guidance list to flag up possibly suspicious mails, rather than a specific spam filtering list.
SORBS are not bad either, they've been around a while but Spamhaus beats most lists heads down for quality and low-false positives.
But I digress, enough about spam filtering lists, good to hear you did the right thing and re-installed from scratch.