Mail.app keeps trying to connecting to old mail server
This sounds like a DNS caching issue still. I know that most web browsers do cache their own DNS as well, and I am sure Mail does, but I think that cache empties after exiting. 

I always try to telnet into port 25 on a remote mail server to test the connection when something is weird. Port 25 is for SMTP traffic, or what sends the mail. If you get a valid connection, you can actually interact with this interface. With your comments though, this probably did not work. 

DNS is a very strange beast, because so many different services do many things, not to mention the different hardware on your network. In this case you have:


router
Mac, but DNS cache and hosts file


In the end, it sounds like you discovered this in your hosts file. I can't count the number of times (I do a bit of web dev) that I set something up in the hosts file and then got confused why something was acting wrong.