DEVELOPERS: When your wallets generate new addresses, you should be putting in a trap that detects if a newly generated address has previous activity, and alert you to the problem which would indicate a weak PNR.
Good point, and lesson learned for USERS as well: When trying out a new wallet, check the blockchain for previous activity on the initial addresses generated in the wallet. That's more than a huge red flag, that's a shout-your-screaming-head-off-to-alert-everyone kind of thing. If keys are being developed like they should, this should NEVER happen within the confines of this universe.
There was news about a month ago about the possibility of hackers releasing wallets with the potential for pre-designated keys. They could then monitor the blockchain and sweep funds from them, even offline, cold wallets, etc., since they would already have the corresponding private keys. I wonder if this is possibly what happened with you. Was the wallet you used a recent release? From a new source?