I'm thinking of getting a dedicated server, but I'm a bit worried about spam. SM/TP charges a $500 fee if an IP gets blacklisted.

One of the sites I currently host has a mailing list. Users have to fill out a form and click on a link in a verification email to receive mail. All list email messages have an unsubscribe link. Is there anything I should think of doing in addition to avoid spam complaints?

Have a read of http://www.spamhaus.org/mailinglists.html and the links at the bottom of that page too.

However, you are always taking a risk hosting an account with a large mailing list - it only takes a few people to contest that they don't want the email and the likes of EV1/SM will often pull the server, definitely if you get on a common RBL.