Okay, I am tossing my old machine with CentOS 5.4. I will be installing a new server with Debian 5.0.

How can I move the POSTFIX data files and email accounts so that I can keep the users from losing all of their IMAP and unreceived POP3 email?

Or, if that isn't available, how could I restore their mailboxes to the new POSTFIX once all of the accounts are re-setup on the new machine?

If you're using mailspool copy the mail spools to the correct location on the new machine, if you're using Maildir copy that to the correct location on the new machine. You'll need to move the accounts with id and such from system auth files (passwd, shadow, group) and ensure ownership is right but generally its a fairly painless process as long as neither machine is receiving new mail at the time.

Yes, it's Maildir. Now, the real dilemma I have is that I am migrating all data and re-establishing accounts on the new machine. Once that is done, I will be taking the old server offline and putting the new one it its place so that it will have the same IP range.

Would you have any thoughts on how to postpone mail deliveries on the old machine, run a batch script to sftp the data to the appropriate directories, and then re-enable the mail for delivery once the new machine is swapped over onto the appropriate IP range?

I'd assume I could shutdown Postfix and just do a fast transfer and swap, but I don't know...

Just shutdown postfix and mail will queue on originating servers for some period of time. As far as moving the actual data goes I'd recommend using rsync.