Can't send outgoing mail from exchange 2003 because ISP blocks port 25
My client has a Watchguard XM22-W firewall/router. They have one server that is the domain controller and email is sent from the domain on that server's exchange 2003. Their Internet is a pathetic 1MBit connection, so they recently added a second Internet connection with another provider that is 10MBit connection. We have configured the Watchguard to use multiwan with the new Internet provider as the primary and the old as failover. The problem is the new ISP blocks outgoing mail on port 25.
The ISP suggested changing outgoing mail to port 587... but that didn't seem to work. Upon further inspection it looks as if I need a smarthost to use port 587, which I don't have. I was thinking of setting up one of my servers at the office to be a smarthost... but haven't found a way to do that yet either.
What's the best way to resolve the issue? Should I attempt setting up a smarthost at my office or is there a better way?