I had something similar with a 6-letter apple account that has never been compromised but I guess got put on some kind of list, because I had to go through account recovery almost every time I logged in, which wasn't a big deal until I got an iphone. Apple support was completely useless. Random old buried forum post in a stall marked "beware the leopard" mentioned the behavior and suggested changing the account name.

Nothing in the Apple site or phone stuff would even clue the user in to what was happening, much less how to resolve it.