When you have really stubborn datalinks like that the only way to remove them is to create a clean file and Append the necessary data in; doing so specifically forces Blender to use data directly linked or associated with any Object/s being brought in, leaving the 'junk' untouched (double-check your link in "Outliner > View > Opps Schematic" view to make sure beforehand though).
The problem stems for the way Blender works with datablocks, basically you're not creating 'Objects' as you would in other applications, but blocks of data, this means that same block can be referenced multiple times without the need to create individualised blocks (as would be needed if each 'instance' was a datablock in it's own right - this is one of the reasons Blender is good with "instancing"). The downside to that is what you're finding, the blocks, being legitimate 'entities' in their own right, are very stubborn, and because they can't be accessed directly in the same way as other Objects, can't be managed easily when associated data no longer has links - in the pre 2.50 versions of Blender this was a really really big problem (as you know) and quite awkward to sort out in situations as you've described.
And yes, when the list of items gets that extensive, you usually have to remove a lot of references before seeing any discernible change, if you have too many it will basically go off the page rather than 'scroll' (as might otherwise be expected).
By the way... holy mackerel! That's the first time I've ever seen that many materials in a file! Speaking of which, if your project is getting really complicated, as indicated, you might want to think about using "Append > Link".. this will allow you to create separate files containing materials you 'link' in to your main project. That way you can make changes to the materials without necessarily altering the main file. Worth thinking about looking at what you've posted above.
