brute forcers would 'bloat' the blockchain and make a shitload of addresses unusable.
Am I wrong?
Yup - that is why I said "trickier" and I don't have a solution at the moment - but it is something worth thinking about (perhaps involving getting an existing NXT holder to provide 1 NXT for said purpose?).
An API call that lets you specify the whole public key of the account you want to send money to, and puts the whole public key in the chain would solve this. You'd have to send at least 1 NXT to reserve the public key.
A bonus is that you could make a 256bit address and load it with NXT at the same time for a paper wallet.