I'd encourage you to re-think the whole "rebuild" idea. There's nothing in the current AD domain that can't be "fixed" by migrating and cleaning it up.
If your decide that you have to rebuild it, you're going to need to do a PST migration of Exchange (since you're running on Exchange 2003 and can't do a cross-forest mailbox move).
Basically, this involves using ExMerge to export all the contents of the original Exchange Information Store to PST files. After you've created the new AD and new user accounts (either using ADMT or "by hand"), you'll import those PSTs back into the new Exchange IS. Finally, you'll need to use something like ADSIEDIT or a script to add an X500 address proxy to each user account that matches the "legacyExchangeDN" attribute that was assigned to their user accounts in the old domain to insure that replies to imported emails function properly (see http://blogs.technet.com/sbs/archive/2009/05/21/cannot-reply-to-old-emails-or-modify-old-calendar-items-after-pst-mail-migration.aspx for details).
Again: Re-think doing this "rebuild" versus migration. Acouple of hours with a competent AD consultant would be all you'd need to idenfity the problems in the current domain and plan for "fixes" as you upgrade to W2K8. You wouldn't need to go thru any of these gyrations with your email and you'll end up spending less time and money for what amounts to a cleaner, better solution.
The "swing migration" is typically done when upgrading one version of Windows Small Business Server (SBS) to another. You didn't mention SBS, and that migration method really isn't applicable in your situation.
You don't need a new domain to do what you're looking for. Hopefully you haven't gotten too far along with it and can start over, because you never want a multi-domain (or worse, multi-forest) Active Directory implementation if you can help it.
The migration from a single-server Exchange 2003 installation to Exchange 2010 is incredibly painless.
Join the server that will be hosting Exchange 2010 to your existing Active Directory domain as a member server. It's not recommended that Exchange be installed on a domain controller. I'll tell you that I've done it w/ Exchange 2007 before and it works fine, but it's not recommended and I've never tried it with Exchange 2010. If you want to make the E2K10 machine a domain controller, though, promote it now. (You really should have a dedicated machine to be a domain controller, and having at least two domain controllers is very helpful. You could continue to use the old server as a DC.)
Verify that your existing Exchange 2003 server has Service Pack 2 for Exchange 2003 installed. If it isn't, install it.
Install Exchange 2010 onto the new server. (Obviously, if you need to move your mailbox database or transaction logs to specific disks do that now before you start moving mailboxes over to the new machine.)
Read up on using mailbox move requests to move mailboxes from the Exchange 2003 Server to the new Exchange 2010 server. It's a very painless process, and there's no configuration changes that will need to be made on the user end.
After all the mailboxes are moved and the users have accessed their mailboxes at least once via Outlook you can begin the process of http://support.microsoft.com/kb/152959">retiring the Exchange 2003 server.
Internet email will continue to flow in and out of the organization via Exchange 2003. You'll want to transition your Internet email flow to the Exchange 2010 installation, though. That will involve creating a "Send Connector" on the Exchange 2010 side, an anonymous SMTP receive connector, and changing firewall rules to divert the mail flow.
You'll also want to be sure that you've got OWA on Exchange 2010 available if your users were using it. That will probably involve firewall rule changes.
Is your backup management software ready to support Exchange 2010? If not, think about that.
You may want to read up on Exchange Autodiscovery. It can have ramifications for your SSL certificate and DNS infrastructure, assuming you don't want to get little annoying warnings from Outlook. Have a look at these for some good background (the second refers to Exchange 2007, but it hasn't change dramatically in Exchange 2010).
You'll definitely want to review Microsoft's documentation on upgrading and coexisting. I'm leaving a lot of little details out, but it's really a pretty painless process.
Best Answer
Personally I would do the Mailbox Migration, I've done it before and had no issues.
Your end users shouldn't see a thing. Last time I did it, I left both the old and new Exchange server online for 4 weeks. This give all users time to login to the computers they used. I didn't have to change anyone manually.
If it goes smoothly your users won't even notice and there will be no downtime except for when you actually are move a users mailbox.