Вопрос следующий - а голосования идут по порядку? Просто по описанию мне так показалось - тогда:
IP | Date | Number_of_poll
где number_of_poll - номер следующего голосования, т.е. человек 1 проголосовал - в number_of_poll стоит 2 - т.е. он может начать только со второго голосования....
А вообще вариант с 20 000 записей нормальный - только грамотно индекс нужно сделать, тогда все будет быстро, по опыту мускул 1 500 000 записей обрабатывает вполне адекватно - и таблица более нагружена была
