Hey there. I'm the one that cracked the Gauntlet PW, and posted it on GameFAQs. Thanks for the interest. It's been a while since I've thought about it. In fact, I DID mention in the FAQ that 'A' passwords do not work. It's addressed in the section labelled 'Vault Combination - Part 1'.
As explained in the password FAQ, the first PW digit (vault code digit) affects all the other digits in the password, by flipping their bits where the vault digit's bits are 1. It's because of this security method that (I believe) they intentionally did not allow 'A' (00000) codes, as that would effectively remove that level of security. But, are you saying that the game will in fact generate 'A' codes on its own? That would be quite a screw-up. Maybe I misread your post on that, though.
Congrats on beating Gauntlet, I never had the patience (and haven't even seen the invisible levels.) My brother-in-law spent months on it, but gave up. Personally I find cracking passwords a lot more rewarding than seeing an end-game screen. :D When I was 14 I cracked the PW to Solar Jetman, and excitedly mailed the completed results off to Nintendo Power. Got back a form letter and never saw my crack printed, then later saw someone that submitted "The Q Code!!" with all Q's, which sends you to some glitch board. That ticked me off a lot (but now as an adult I understand why they wouldn't want to release full password crack info for a game...)
I should dig out my old Solar Jetman PW crack papers, and post it sometime as well. I solved both with basically the same method, which did not involve any ROM cracking of any kind. Just observation and deduction. However with the advent of GBA flash cards w/ NES emulators (read - SAVE STATE), I can solve them MUCH more quickly. (Man I remember having to put all those Solar Jetman passwords in by hand for hours...) I also made some progress on Faxanadu, but never finished it. The coolest part of PW cracks is when (like in Solar Jetman) you can generate working passwords that the game could have never given you, and see glitch boards and truly weird things.
Anyone interested in having a particularly troublesome/popular game password cracked? (Hard to find one more troublesome than Gauntlet though, I imagine...)