It took me hours to find out that KMail only can verify PGP/mime signatures with cryptplug installed. So it would be nice if cryptplug could be a dependency of kdepim which contains kmail (at least in version 3.2 beta). There is (AFAIK) a USE-flag named "crypt", this could be used for this.
Fixed, thanks for the report.