USCIS are quite clear about this
USCIS Form I-9 details the options available to prove Identity and Employment Authorization.
A Permanent Resident could present their PR card, or an I-776 singularly which illustrated ID and EA. OR they could present for example both a state issued Driver License plus a non-endorsed SSA card.
The problem appears to be that MS were insisting on a specific ID, which is verboten.