I wonder if it makes sense to imagine some key-stretching function f, which for different values of x, would take vastly different time to find y=f(x) or y=f(x,s) if we add a salt, like for x1 it would take 1 nanosecond to execute the calculation, but for x2 it would take 1 minute.
Maybe you could do it (inflated variance) but generally I think it doesnt help because the attacker can just grind them all in parallel (multi tasking if necessary) so the uneven work factor will be removed. You could think of knowledge of which bucket the real key is in as the salt, ie if you make a random salt in PBKDF2 or Scrypt and delete it as I suggested somewhere in the above thread (not a new idea, Rivest et al proposed it in their time-lock puzzle paper) then you can have instant setup, but a lot of work to decrypt. If you keep the salt then it can be very secure.
eg if you have a server with a password hash (or public key/address created with it), but the user has the salt stored and the salt is 128-bits, the server can verify when you get the password right, but the server (nor any hackers who break in and take the password hash db) have no hope what-so-ever to grind the password. Actually I used that design in oneid.com end-2-end secure auth model in several places. (I am a crypto consultant to them and a few other companies).
The limitation for general use is you can think well the salt is on your disk, what if you have a disk crash. In which case the salt is so large you'd just as well call it a key and be done.
Adam