You didn't specify your email client.
If you're using Outlook (Express), the safest method is selecting all messages in a "personal folder", and dragging them into a real folder in another window. This copies the messages as separate files; once you reinstall Outlook, just drag them back in. You'd have to do this for each folder. Same goes with Address entries.
I didn't like the Export feature alternative, because it exhibited crappy compatibility even between MS products.