I've tried to trace this down further.
I use gtk_cell_renderer_text_set_fixed_height_from_font(renderer,1);
When looking into gtkcellrenderertext::get_size()
the height is calculated by:
2*ypad+
row*PANGO_PIXELS(row_height)

to me this misses some padding for the focus rectangle.
Is there a standard of how the focus is drawn (size and appearance)?

I've not yet found out who is handling that. The only parent class is
GtkCellRenderer().

Created attachment 45123 [details]
testcase that shows wronge focus drawing

build with:

gcc -Wall -g `pkg-config gtk+-2.0 --cflags --libs` treeview.c -o treeview

I've now added some output to gtktreeviewcolumn.c. The problem is at the end of 
gtk_tree_view_column_cell_process_action();

if (action == CELL_ACTION_FOCUS)
  {
    if (min_x >= max_x || min_y >= max_y)
      {
	*focus_rectangle = *cell_area;
	/* don't change the focus_rectangle, just draw it nicely inside
	 * the cell area */
      }
    else
      {
	focus_rectangle->x = min_x - focus_line_width;
	focus_rectangle->y = min_y - focus_line_width;
	focus_rectangle->width = (max_x - min_x) + 2 * focus_line_width;
	focus_rectangle->height = (max_y - min_y) + 2 * focus_line_width;
      }
  }

always using 
*focus_rectangle = *cell_area;
fixes the behaviour for me and also resolves :
http://bugzilla.gnome.org/show_bug.cgi?id=169464

Further this would allow to skip all the calculations above. Am I overseeing
something?

While I agree that the cell focus drawing may need improvements, always drawing
the focus around the whole cell is likely not the right solution. 

It is intentional that we draw the focus rectangle over the neighbouring rows,
IIRC my discussions with jrb correctly.

We did not take the focus-line-width into account in validate_row(). Also, we
didn't take the focus-line-width into account when calculating the cell_area y
and height in gtk_tree_view_column_cell_process_action(). Both have been fixed
on CVS HEAD, so your issue should have been resolved.