Default to only showing 'Live' entries in CP?
I'm adding Brad's comment here as an answer as I think it addressed indirectly this issue:

Craft 2.3 should fix the performance problem of Structures and Categories with large amounts of entries.