Have you considered implementing support for vanity addresses?
Granted they inherently mean re-using addresses, but at least Armory could give maximum security.
The user could ask for a (standard) receive address from Armory and send it to a vanity address generation service.
The website would send them back a multiplier that multiplies by the public key to give the vanity address.
Importing into Armory would be a simple matter of providing
<Public key>, <multiplier>
Armory would find private key matching the public key and then multiply it by the multiplier. This gives the vanity address's private key, which only the user knows about.
The list of <public key>, <multiplier> pairs could even be saved in plain-text and would have to be backed up.
The service that generated the address would probably store them too, so even if a person lost them, they could probably get them back.
The private keys associated with the addresses would be protected by the Armory's paper backup (as long at they have the multiplier).
You pretty much get the same backup safety as Armory, but for vanity addresses.
In addition, you are relying on Armory to keep things safe for the user.
All transfers associated with the vanity address would be handled by Armory. This would give better protection of the vanity address's private key than using some of the other systems (which used weak RNGs).
You could implement a "sweep vanity address" system, which moves all funds in the vanity address to other addresses when the user hits the button (or maybe periodically).
How does Armory do the ECDSA? There has been talk of using Hash(Message, private key, random number from PRNG) as the random number, instead of using the RNG of the system directly.
