Its actually every possible combination up to 63 characters for every possible essid. For each essid you need a separate table containing the password hash for every combination up to 63 characters. Just the 1000 most popular passwords for a given essid is around 30MB.
Short term use an oddball password AND essid containing non standard characters. Whenever you change your password you also need to change the essid. If not they will already have built the table for your essid and they will be able to break the new password within minutes. If you change the essid and password combination frequent enough they will not be able to generate the new table before you have moved on to the next combination. I would think once a month would be very safe and once every three months would be pretty safe.