I'm in agreement with everything that Massimo says. I wanted to expand re: "existing accounts and access".
For Outlook to remain "connected" to the mailbox it's really, really straightforward.
I'd recommend bringing up the new Exchange Server computer on the network where the current Exchange Server computer is located. Do everything that Massimo said re: the Routing Group (and, if necessary, creating an Active Directory site for the remote office, etc).
You'll perform a "Move Mailbox" operation on each mailbox that you want on the new server. I've found that it's best to do this when the user doesn't have Outlook open, but it can be done "hot", too. (I've found that Outlook can get confused when Cached Exchange Mode is enabled and the mailbox gets moved to another server. Your mileage may vary.) Performing a "Move Mailbox" over the VPN is going to be tedious and potentially failure-prone. That's why I'd recommend staging the new server on your existing LAN first and getting all the mailboxes moved over. Create your public folder replicas at this time, too.
Since your users are already used to the "speed" (or lack thereof) of accessing their mailboxes they won't notice any speed difference during this transition. Their Outlook clients will automatically "update" to reflect that the mailbox is on a new server (this is a very, very nice feature). Once you've gotten all the mailboxes moved, ship the server out to the remote site, change its IP address, plug it into the network, and get its DNS registration updated.
If your users are only using Outlook to connect to the Exchange Server computer you can be "done" at this point.
If your users are also using Outlook Web Access, POP3, IMAP, or ActiveSync over the Internet, though, you're going to need a strategy to facilitate their access. Presently, having a single Exchange Server computer you've never had to worry about "Front End" and "Back End" servers. When you have multiple Exchange Server computers hosting mailboxes you'll either have to: (a) allow users to connect to OWA, POP3, IMAP, or ActiveSync running on the server that hosts their mailbox, or (b) deploy a Front-End Exchange Server computer that clients connect to for these protocols.
The front-end/back-end server method is the easiest to use, but requires an additional Exchange Server license. Users have one URL to connect to for OWA and one hostname to use for POP3, IMAP, and ActiveSync.
Alternatively, we have some Customers who have two Exchange Server comptuers and users who use OWA. To get by "on the cheap", we've configured two (2) different public IP addresses and names for the users to connect to-- one for each Exchange Server computer. The user has to connect to the correct URL / server to access their mailbox, though.