It doesn't look like you're showing all the css in your example (is there a div or two acting as the border?), but have you tried removing the height attribute and setting the padding-bottom to padding-top's value (9px)?
Sidenote: you don't need div#search_icon, your input could have the following background:
background: white url('images/magnifier.png') no-repeat right NNpx;
Your problem is that you're not taking into account padding on the input box when you're specifying its height.
You're specifying a height of 32px, but any padding gets added to that, so the height of your input box is actually 32 + 9 + 4 = 45px. The cursor is being vertically centered in the 45px tall input box, but your border is around the 32px tall div. Change 'height: 32px' to 'height: 19px' on the search input and it works.
I (very highly) recommend using Firebug. It's very useful for figuring out these sorts of things.