In a typical X.509 PKI implementation, the CA is somewhat heavyweight. Far more than just a special CA certification, running a CA typically implies running a web service to service certificate requests, perhaps an OCSP responder, publishing CRLs regularly, perhaps an SCEP server... This heavyweight notion works well for large enterprises, but somewhat less well for small deployments like your own. Suck it up, though, because there really isn't a good solution for lightweight deployments.
What I'm trying to say is that yes, the "correct" solution in this case is for the CA to check to make sure it hasn't issued a certificate to that user before issuing a new one. This is a fairly annoying extra requirement for a small deployment, but an utterly trivial task next to all the other crazy things a "standard" X.509 deployment is expected to do. I feel your pain, and I know it's not very elegant, but the easiest solution in this case is to just keep a list of all the ID codes served so far and fail if one is resubmitted.
In an ideal world, you'd be able to map the unique identifier you're talking about to a unique key, so re-issues wouldn't be a problem. However, that's not doable with X.509.
PS: I'm assuming here that you in fact want to do what the question title says: assign only a single certificate to each user. If, instead, you only need to prevent double-voting during the election, you could just record the subject unique ID of everyone who's voted already, which would make having more than one certificate for the same unique ID useless. Changing the logic of your voting application is probably easier than changing the logic of whatever CA service issues the certificates.