It's also unacceptable that people are waiting several months and even indefinitely in some cases to have their accounts restored even with a signed message already verified by others.
Maybe an account recovery fee would help speed things up a bit?
But currently an account fee with bitcoin would not make sense because of the high transaction fees.