Just a data point for anybody in the future:
I bought the Tchibo surf stick back in December (well, actually my brother bought it, but I have it now
)
I arrived in Germany Friday night. Saturday morning I stopped at a Tclibo shop, bought a €20 topup (yes, I realize an O2 one should work). I fired up my laptop (Macbook Air) stuck in the stick and fired up the "Mobile Partner" software. Clicked on "Guthaben verwaltungen" (or something similar), entered the voucher number and I was off. The internet came right up and has worked flawlessly since. It went much more smoothly than I figured (because I am a pessimist
)
Of course, the landlord of the apartment I use has replaced his crappy WiFi with a fast DSL connection and a good router, so I don't actually need the Tchibo service as much as I had figured.