I just did this in Germany last week, it has gotten a lot more painful. They now want an official document showing your German address (Personalausweis or Meldebescheinigung) making it impossible for foreign visitors to get a German SIM. Two years ago it still worked with only my passport.

Next time I'll just do roaming on a prepaid card from my home country, unfortunately my current provider doesn't support roaming in Germany.