I dont know if this is too late or not, but here's my 2 cents worth.
What I would do would be to have the ISP add the new server to DNS, change the MX priority to 10 (or 5, the lower the number the higher the priority) on the new server, let the new server bring in the internet mail for a...