> In Germany, rumor was you basically had to be a German citizen to get a SIM; that turned out to be untrue but I cannot remember if I gave them my (EU but not German) passport

From my experience, you do have to have your passport with you when getting a Sim. They usually make a photocopy of it. (This was from O2)