How do I force unique values within a multi-value set?
It might be easier to filter the autocomplete results using JS. You could either extend the prototype being used by Drupal or use some sort of trigger for when the results are being displayed.

I don't think that server-side solutions such as session variables and so on are practical as there's no guarantee that the results of previous calls were actually used by the user. Similarly, hacking the autocomplete feature to perhaps send existing values along with current user input is inherently impractical.