According to Kaspersky, even if you format your hard drive, an infection could be persistent if it lies in the firmware.
If you expect to be targeted by those with access to firmware-based malware, it may be far safer to flash the firmware yourself with a trusted copy of your hard drive's firmware, and then format it.
UPDATE: Regarding the USB drive being scanned and formatted, that doesn't matter if there's an issue with the USB stick's firmware. Bad USB comes to mind. Your anti-virus suite is not likely to be able to scan the firmware. If I'm wrong, I'd love to know.
I'd like to answer some of your questions here.
Did it already happen that a device was infected before the first customer use?
Yes, it's being referred to as Supply-Chain Interdiction. What this means is that when you buy computers, or computer hardware online, and you're targeted, it may likely come pre-installed with malware.
(In case it matters: I have a Ubuntu Linux system)
That doesn't matter much. "Hacking Team," a company that develops malware for use by anyone who can pay, states that they have support for the top-5 distros on DistroWatch. If you visit distrowatch, you can see that the top 5 are as follows:
Which could easily mean that anything based on those distros are likely affected as well.
Finally, as I've said before -- if you're really worried about being targeted -- I suggest acquiring a copy of your hard drive firmware and flashing it, then formatting it.