U.S. Treasury checks are treated differently than other checks. They are governed by 31 CFR Part 240. This regulation outlines the requirements for endorsing and presenting the check for payment, and the requirements are more strict than other checks. In addition, the regulations give the government extra ability to refuse payment of the check if it is not endorsed properly that other check writers do not have. As a result, banks are overcautious with treasury checks.
My credit union is normally very lenient when depositing checks into my wife and my joint account. My wife or I can deposit checks made out to either of us, and as long as we are depositing the entire amount into our account (not cashing it), the checks don't even need to be endorsed.
However, when it comes to government checks (i.e. tax refund check), they insist that the check be signed by both my wife and I, even though we are simply depositing it into a joint account.
Even with this policy, my credit union does not insist that we both be present at the teller window, just that we each sign the check. Of course, as you and mhoran_psprep have pointed out, it would be ridiculous for them to insist we both be there, because we could deposit it by night deposit, by mail, or by any other after-hours method.
To answer your question, nowhere in the regulations that I could find does it insist that both parties be present to deposit the check. However, the regulations do insist that the financial institution ensure that the check is not endorsed without each "payee's consent or authorization."
Perhaps your bank has been burned in the past by treasury checks getting returned. When a bank is setting policy, they really can't expect their tellers to be familiar with all the details of every regulation. They have to set policy that covers themselves legally and are easy to be followed by their employees.
The fact that it was not going into a joint account might have something to do with it. But I agree with you that the policy does not make a whole lot of sense, and I don't think that the second bank was remiss.