Exchange is an email system where email does not download permanently onto a client computer. All your mail (and calendar events, etc.) stays on the Exchange server at all times (your computer can be set to cache messages for speed of access, but even then they aren't deleted from the server). Therefore, you don't have to worry about some messages being accessible on one computer but not the other.
The exception to this is if you archive your email to a separate mailbox. Archiving moves the messages from the Exchange account into a PST file on the local computer. These messages won't be available from any other computer (PC or Mac), but you can always move them back into the Exchange account if you need them.
If you're using Snow Leopard, the Mail app has built-in support for Exchange server. I do this for two different accounts: I use Outlook 2003 or 2007 for Windows computers, and Mail.app on my Mac.