How do you encrypt ALL of your mail folders, in case your laptop gets stolen?

It looks like Truecrypt is the only solution?

Yup, use Truecrypt.