How can we avoid the shake when we hover over an element and set its border?

Alternatively, when setting the border add a negative margin of the same size.

The usual solution to this problem is to start off with a transparent border, then give the border a colour on hover.

I've updated your fiddle with this technique:

http://jsfiddle.net/s3N2h/1/

CSS and JavaScript:

#my_menu li {
    border: 1px solid transparent;
}

li.hover(function() {
    $(this).css('border-color', 'white #808080 #808080 white');
}, function() {
    $(this).css('border-color', 'transparent');
});​