Hmm, how about 

typedef void (*GtkTreeViewSearchPositionFunc) (GtkTreeView *tree_view,
                                               GtkWidget   *search_dialog,
                                               gpointer     user_data);

void
gtk_tree_view_set_search_position_func (GtkTreeView                  *tree_view,
                                        GtkTreeViewSearchPositionFunc func,
                                        gpointer                      data,
                                        GDestroyNotify                destroy);

Note that this adds user_data, so we'll have to adjust current callers.
Do we also need

GtkTreeViewSearchPositionFunc
gtk_tree_view_get_search_position_func (GtkTreeView *tree_view);

?

Looking at gtk_tree_view_get_search_equal_func(), I notice it returns
a pointer to a static function if the default function is used. Is that
ok, or should it return NULL in that case ?

Oh, btw. Is this also supposed to allow reparenting the dialog to somewhere in else ?

Yes, people have also wanted to support their own entries.  For example, a list with a search entry above it, in the widget heirarchy.

A simple search_position_func is not really suitable for achieving that, is it ?

No; we need more than that.  We originally planned to add an option to pack the search entry in another container.  But maybe it is cleaner to have the user supply their own entry and have GtkTreeView connect signals the signals on it.

Adding _{set,get}_search_position_func() looks like a nice idea to me.  Next to that it might be nice to add something like:

  void gtk_tree_view_search_set_entry (GtkTreeView *tree_view, GtkEntry *entry);

which will then override the "built-in" popup window with entry.  Or maybe gtk_tree_view_search_{attach,detach}_entry()?

If we can settle on a name I can implement this ;)

*** Bug 72280 has been marked as a duplicate of this bug. ***

I might go with set_entry(entry)/set_entry(NULL); to set/unset the entry.  Otherwise, it looks good!

CVS HEAD now has
gtk_tree_view_get_search_entry()
gtk_tree_view_set_search_entry()
gtk_tree_view_get_search_position_func()
gtk_tree_view_set_search_position_func()