We have seven servers total but these users in question only have access to 3 of the servers:
DEV - Version: 9.00.3042.00, SP2, Developer Edition
QA - Version: 9.00.3042.00, SP2, Enterprise Edition
Staging - Version: 9.00.3042.00, SP2, Enterprise Edition
Note all are 32 bit.
What version are you on and can you identify the permissions your test user has for all databases? I have two scripts that can help you with that (see attached). One is for server permissions, the other is for individual database permissions. This way if SQL Server is doing something under the hood this should uncover that and I can compare the permissions to my users.
I personally wonder if it is tied the the certificate. I inherited the databases and it appears some of the ## system accounts have been dropped.