yeah i agree, 13000 emails is way too much... there must be a pretty good reason to have so much concrete in the archive!

Definitely Phish's idea to archive into separate pst files according to user information would be the best start. Else, just copy the whole pst file to a new HD, and then start OE with a clean identity and try to follow the 7 best practices !