No, I haven't got around to working on it yet.

I like to think of future problems I'm facing two or three weeks in advance of me actually starting on it, while working on other prerequisite code.

I'll post if I come up with a solution or if I need more advice. I'm still thinking Erik Rufelt and JoeJ are on the right track there.

Gather dependency data first, and group them into buckets along with type. For example, a tree that occludes three rocks and another tree goes into a bucket precisely with trees that occlude three rocks and a tree.

Then bubble sort the groups based on the following condition: A > B if no item in B occludes any item in A.

Once you've bubbled the item, merge it with any nearby group of the same type (ignoring dependency information) and resume bubbling the next group.

This isn't something I recommend actually trying, but it should at least do what you're asking for. Constrained sorts aren't the type of problem with an easily canned solution. There's still a couple holes in this, so you'll probably have to do something exotic like alternate bubbling directions.

This definitely won't be optimal (a lot of calls to Overlapping), but can't you just use a sorting callback that sorts on depth for overlapping items, and otherwise sorts on render state -- similar to:

int CompareDepth( float a, float b )
{
  return a < b ? -1 : (a > b ? 1 : 0); //or whatever conventions your sorting library uses...
}
 
int Compare( Item& a, Item& b )
{
  if( Overlapping(a.bounds, b.bounds) )
    return CompareDepth( a.depth, b.depth );
  else
    return CompareStates( a.renderState, b.renderState );
}

Assuming your sorting library takes a callback for comparing items.

I don't think that's a strict weak ordering.

Let's say a overlaps b, and b overlaps c, but a does not overlap c. a could be less than c with respect to depth, but greater than c when comparing state. I really doubt a sort comparison designed this way works for transitive relationships.