Thanks Tim, I did a test with fading-ou/markers markers as well with jquery animate, which underneath would be pretty similar to your solution.
The thing is that it's a complete performance killer with a lot of markers, at least in my case.
Conceptually I'd like the following different solution of having each featuregroup be represented by a separate DIV in the dom (which is not the case in leaflet at the moment). Then you would require only 3 divs/featuregroups. 1 for fadein-markers / 1 for remaining markers / 1 for fadeout-markers plus of course some juggling of markers from 1 div/featuregroup to another.
This allows just animating 2 div's/featuregroups with all the performance benefits (performance is independent on the nr of markers.) Animation can even be done with css3-transitions on newer browsers. I implemented this in mapbox.js, which does use multiple 'group-layers' to represent markers, and it works great. (I had to refactor to leaflet for other reasons)
I'm parking this issue for now, but may revisit it by looking into hacking leaflet by providing the '1 div per featuregroup' functionality.
Cheers,
Geert-Jan