I'm using Xemacs 21.1.12, Gnus v5.8.8, GnuPG 1.0.4 and mailcrypt 3.5.5. I actually also saw this behavior with gnuPG 1.0.2 (which caused me to upgrade).
I had a message sent to me from Microsoft-Outlook-Express-Macintosh-Edition/5.02.2022 and PGPfreeware 7.0.3. When trying to decrypt it in xemacs/gnus/mailcrypt I get the error that "The message was corrupt." However, if I start 'gpg -d' from the command line and cut/paste the message to stdin I was able to decrypt it.