Have any security researchers checked GMX out yet? Maybe they suffer from a lack of bruteforcing protection ala iCloud.
You can do SMS, but then you need phone numbers for users. Requiring "alternate email" is kind of a nightmare.
I wish someone could build a "account recovery as a service", with different levels of escalation. It would be fun to spec it out, but I have no time to actually set it up, since it's more a business vs. just some servers.