The biggest issue is your domain getting blacklisted for whatever reason. It may look like the name of another spammer's domain name. The server you rent may be colocated on a rack with a spammer's box (or a box owned by spammers) and have weird reverse IP SNAFUs. Your very server may not have the latest 0-day patch and bet 0wned by script kiddies and, bam, again... Blacklisted.
Note that I do NOT know much about email servers and that is precisely the point. I eat iptables rules for breakfast, I can set up a Debian server from scratch and I can certainly configure a mail server. But there's more to it than meets the eye. Been there, done that. And we got burn.
I don't know "why", but all I know is that we had problems!
tl;dr: 30 team person startup and we tried to use our own mail server. Too many problems. We moved to Google Apps for domain and all our problems were fixed...
At conferences, especially security conferences, I tend to ask if anyone ever heard of a Debian base installation being hacked if it has auto-updates or is manually updated once a week. So far, my count is 0 and when asking self-proclaimed hackers, they also tend to agree that Deiban stable installation is very secure. The installation I got from 1999 is still running, and the count of breakins are 0. to add on that, it has no firewalls. I kind of wonder what happened that caused your server to be hacked. Insecure password?
As for using a previous owned spammer domain, I strongly question that logic. Black lists tend to be both conservative and done by copy-pasting. A blocked domain abcd will not block abc or abcde. If the block lits do not see mails from abcd within a month or so, they also tend to remove them to clear up space. This time frame is also way below common domain name expire dates.
Regarding reverse lookup, I assume that 30 team startup bought a company network contract from the ISP. Such deals should include support and static IP, which mean reverse lookup is a single email away from being done. Co-location contract might be different, but I wouldn't know.