When and why to deprecate filesystems

> The part on who should do it is a problem :-)

Well, the one who wants to deprecate should make sure the replacement is in place, IMO :) (Which doesn't necessarily means doing it themselves, but at least finding someone)
Besides, testing FUSE filesystems could possibly be done with a single test suite ran much less often as the code is expected to change less.
Another idea to add work to someone else (TM) would be to require this to introduce new filesystems. It'd be nice to other OSes to be able to read whatever Linux brings and it would make it trivial to deprecate them later, as it's much easier to write this when the know-how is already in your head rather than reverse engineering the work someone did 20 years ago.