Atlantic.net will let you have a virtual private server for $9/month. A fixed IP will be a few bucks more, although I've had the same incoming IP for years and they have never changed it.

Running your own mail server is tricky. I pulled my hair out trying to get all the authentication shit in place to allow gMail to accept incoming messages. Definitely not a beginner-level task.