First and foremost, static IPs are a must. Second, make sure those static IPs haven't been misclassified as dynamic or dialup. Then get reverse DNS setup properly (some providers won't do this). Then setup SPF. On top of all this, make absolutely 100% sure you don't run an open proxy. Then keep an eye on blacklists and your logs, and be ready to call and deal with obstinate tech support for hours on end. DKIM, and having some way to reject emails at the envelope stage (to save bandwidth, avoid double bounces, and punish the guilty rather than bouncing to innocent parties being Joe-jobbed) are also good ideas.
It's not horrible, IMHO, but it's not necessarily a cake walk either. You might need to have an understanding employer so that you can take off for half a day to deal with things.