There's nothing special when using a Huawei stick under Linux. Years ago it was a bit tricky since Huawei sticks do appear only as thumbdrive under any OS upon first plug-in and only after a so-called "USB ModeSwitch", which Mobile Partner would perform after installation, the modem components would appear as additional USB devices. Huawei never supplied Linux software and most Linux distributions didn't support this "USB ModeSwitch" natively, so you had to do what is described
here. Anyway the problem was to get the sticks running under Linux, not to use them later again under Windows.
Since your stick has been detected correctly on your Windows computers after having used in under Linux and you could connect there doesn't seem to be any problem in the OS-hardware-relation.
None of the network-specific settings (APN etc.) made under the OS is being stored on the stick - it actually doesn't store anything besides the write-only partition, that contains Mobile Partner. Also there's no reason for Tchibo to block your stick (if they did it couldn't even register on the network and if they had reason they would rather block your SIM).
This rather sounds like a routing problem of Windows. Did your Windows computers have any other active network connections before you plugged the stick back into them? I've had similar problems when using Wifi and LAN simultaneously and interrupting one of the connections for a moment - Windows seems to decide randomly which network connection to use for internet access and sometimes it routes data through a network connection, that actually isn't connected to the web.
If this happens once more to you try to disable all other network connections and reboot your system and then reconnect through Mobile Partner.
Since I've been using O2 for the past ten years as most of my friends do, I've never had noteworthy outages. I don't think you had a network problem but rather a software problem/bug under Windows.