The GPG plugin thing for Mail has a preference panel with an option to always use OpenPGP/MIME.

Enabling this resolved the problem.