Version:           1.5 (using KDE KDE 3.1)
Installed from:    Mandrake RPMs

Tools / Find Messages seems to search the messages as they are stored on the disk (like grep). As a consequence the still gnupg-encrypted messages are searched, and of course the search text isn't found.
I searched for some text contained in both encrypted and non-encrypted e-mails, it only found the non-encrypted ones. I also searched for a small piece of encrypted text (copied from the mail source) which was found. So, in fact encrypted mails are really searched but without decrypting them.
Obviously this isn't the expected behaviour. KMail should detect encrypted mails, decrypt them, and then only search them. If this slows the searching down too much (for large inboxes with many encrypted mails) a checkbox to disable searching of encrypted messages could be added to the Find Messages dialog. Nonetheless encrypted mails should really be searchable.