The thing is that many people think that their password is safe as they use something of similar size/complexity on web-sites. However, on a web-site the attacker cannot really brute force it until he has access to the encrypted password file or a hash of the password (maybe with some seed). Without this the hacker is left with a few attempts a second (through the web-page login), with the risk of locking the account he tries to gain access to. With brainwallets the attacker can start brute forcing with trillions of attempts a second just by looking at the blockchain. (or in the case of a paper backup, once he has access to the encrypted private key).
I really want Mycelium users to use safe and verifiable mechanisms that do not lure them into using something that they think is safe while it is not.
So how about if we convert the attack on the blockchain into an attack on a website instead. We can do it by adding a protocol to the client to save the strong key, encrypted with the human password, on S3 Amazon cloud or Dropbox or something.
Only the strong key shows up on the blockchain and an attacker would have to dig up the user Dropbox account before conducting a dictionary attack.
The unencrypted strong key never leaves Mycelium.