So if I'm getting you right, you think that it is of tremendous importance that a user not be asked, in their 5 question run, whether to choose Good or Evil twice.

And you're willing to take a MASSIVE performance hit to guarantee that, for all users.

OK, let me take a wild stab in the dark: you've got over 1,000 unique pairs in the database. You ask the overwhelming majority of users 5 questions. The chance of a user getting 5 unique questions, if you just pull them randomly out of the DB, is about 99%. And that would be Pretty Darn Fast to calculate.

Or, here's a cheap trick for you -- partition your table of questions into 5 groups. A really simple way is to take primary key mod 5, but if you want to do it better you just hash the input and then take mod 5, then store that in a group column. For the first question, choose randomly from group 1. For the second question, choose randomly from group two. etc. By construction, it is now impossible to ask the same user the same question twice.

Which means you don't have to store a user's prior votes at all. Just store counts.

There, enjoy your million-fold performance increase.