Captcha

имхо, лучше по крону, чтобы некий кэш их был. либо искать более быстрые алгоритмы =)

Смотря от чего защищаешься. Если, скажем, от DoS-а - задалбливания вычислительно тяжелой странички, то однозначно предгенерить. Если от спамеров в личном блоге (а "штук 500" наводит на примерно такие мысли) - то ХЗ, может проще и на лету.

а имхо лутше юзать что небудь типа recaptcha, и избавить себя от гемороя и если найти время, да ище а кустомизировать ту же рекапчу, тогда уж щастью не будет приделов