The attacker would not search for the private keys alone, he would calculate the private/public key and their corresponding address for all passwords up to a certain length (depending on his capacity), and store them in a table. Then he would scan incoming blocks for transactions that send coins to addresses that match his table. This allows him to harvest transaction outputs sending coins to addresses based on private keys that are generated on weak passwords. With one such table he can attack everyone using this scheme in parallel.
If the key generation is based on both a password and something that is globally unique (such as an email address) the attacker will have to either calculate really really big tables (unfeasible) or make a targeted attack against a single user (provided that he knows his email address), yielding much less profit.
How much of a length do you have in mind? The deterministic generators in existence now and that are proposed require passphrases with a minimum of 20-30 characters... this guy's table would have to have something like 10^37 entries, and he would need in excess of the world's capacity in hard drives to store it. In addition, calculating ECDSA public/private keys is already a very slow operation, he would probably need in excess of his lifetime to produce just 10^20 keypairs and the GDP of a small country just to pay for the electricity, let alone 10^37. This attack is effective against the fool who chooses "john's bitcoins" as his passphrase, but not against someone who uses a program that refuses to cooperate with a poor passphrase.
Although I agree that the linked wiki article discusses it and recommends the user enter a "salt"... what practical difference would there be between the user entering a "salt" into a separate field, versus simply appending some extra characters to their passphrase? They will be concatenated anyway, so none from what I can tell. Salt in most other contexts is not something chosen by a user, rather it is something added by an application outside the user's control.
They aren't really concatenated, but seperate inputs to scrypt, which generates the seed used for deriving keys. The idea with the salt is that it is easy to remember, unique, and not a secret. In practical terms it allows for stronger security without having the user remember/keep-secret a longer password. In a UI I would always keep this as two seperate fields, as this makes it easier for the user to understand that there is a secret component and a unique component of his wallet.
With deterministic wallets we cannot rely on a central component generating the salt. We need the salt to be the same whenever we wish to recreate the wallet.
I still don't get it. One component needs to be secret (but not unique) and the other needs to be unique (not secret)?
The whole point of a passphrase is to be both unique and secret. If they're both, and they're long enough (entropy wise) that's all that's needed.
This completely makes sense in the context of using scrypt on, say, a website where there's a database, and per-user salt is stored separately from the user's brain. If scrypt is the algorithm of choice, and the algorithm wants a salt, and the user has to remember it, why not just define the first n characters of the passphrase (or the hash of it) and call it the "salt", rather than burden the user with caring about the difference. By demanding that the user understand "salt" to use a payment system, the size of the potential audience willing to use the payment system just gets quartered or worse.