Any other ideas about how that happened?
The first and easiest possibility would be that the website you've used to generate the paper wallet wasn't only showing it to you, instead it also made a copy of that paper wallet for the website owner.
And at some point, when he noticed you've funded it, he stole your money since he had too the private key.
Another discussion is about what you've done with the paper wallet an how you've stored it. If anyone else copied the private key, he could steal your money.
A paper wallet as you've done it is a private key and an address. Those can be kept on paper, but some keep it (wrongly!) in e-mail or cloud storage, giving others the chance to steal.
Plus if your computer has malware, for example, it was open to the internet.
These are the first possibilities coming into my mind.
Another thing is your opinion about one method I'm thinking for generate a paper wallet in bitaddress.org. Everybody tells that the bitaddress' website is safe. Is that so?
The idea is to enter in the website and switch off the internet. The next steps will all be done without any internet:
- generate the wallets
- restore the windows, erasing everything
- take out this HD, connect to my other notebook and format it using the program Eraser, which records random information in the drive
- return the HD to the previous notebook and install Windows again
Only now, turn on the internet.
Any risk in this procedure?
I don't know how good is bitaddress. If people say it's OK, fine, but such a tool can easily generate the keys even by a certain rule and make it easy to recover by the site owner. I would use a wallet to generate the private key.
Apart of the first step and using a paper wallet generator, the rest of the steps look pretty good (although booting from an USB stick with a live OS with no persistence would achieve that easier).
I would use Bitcoin core (offline, without downloading blockchain) or Electrum (offline) at first step and, as a later step, I would recover the wallet from the private key and make sure the address is the one expected (so you avoid surprises there too).
Later edit: if you invest into amounts like 0.4 BTC, is it so difficult to invest in a hardware wallet? It would be safer and easier even for making yourself some sort of paper wallets, if you still want those.