I did try to implement the soultuion Yves M. suggested:

Code:
private:
  Leaf& _search( const LeafAttributes& ) const
This unfortunately just lead to the point that I had to use const_cast's inside the implementation. Most notably I have subclass Branch, which is both a Leaf and a Tree (hmm, something wrong with terminology here, but it does make sense) and overloads the implementation of _search. So, somewhere I have then:

Code:
class Branch : public Tree, public Leaf
{
[...]
private:
  Leaf& _search( const LeafAttributes& ) const
[...]
}

Leaf& Branch::_search( const LeafAttributes& ) const
{
  if (...)
    return *const_cast<Branch*>(*this)
}
This is not really prettyier than the original solution.

So I'm just starting to accept that there is no magical third way. I either can do two separate installations (const and non-const), or I can use const_casts to have one use the other.

Thanks for the comments anyways.