CounterParty does something similar… for free are assets named A00000000vanity.
Obviously onion addresses are similarly obscure by default, so random longer address could be free and shorter ones at a price… but it still resolves to how you sell the first round of brands, price could be made prohibitive but is pandering to that risk worth the price all must bare.
I suggested before an alt approach would be to allow vaults to mine namecoin-like access to vanity names. See PublicIDs released as reward for vaults? cf namecoins - #3 by davidpbrown