Are the tags located in a place where you could give them background color all of the time? If so, does setting their background color when :hover is not activated still cause their height to change?
As a note, I can't reproduce this given HTML matching the rule you described, so the problem may be coming from somewhere else higher on the page.
<!-- This does not display the described behavior -->
<div class="options">
<ul class="tags">
<li><a href="#">c++</a></li>
<li><a href="#">not-programming-related</a></li>
<li><a href="#">cheese</a></li>
<li><a href="#">barnacle</a></li>
</ul>
</div>
The best thing I can suggest is to do what mercator said and give the element layout.
EDIT: Just a shot in the dark, but you may want to try setting a value for line-height on div.options.
EDIT 2: After seeing your screenshots I recall that I have had this problem at work before, and the fix in my case was to add position:relative;
zoom:1;
to the container (or maybe the links, I forget!). Try that?
EDIT 3: After googling for some solutions, you may want to try setting the height if your container explicitly. If this doesn't work, I have no idea what to do!