When I sort contacts by Company (lastname, firstname) they no longer appear in the interface. It seems like they are deleted, because they do not show up in the search. I have noticed also that deleted contacts do not clear the page index so even though I can only see 7 contacts, the scroll option at the top says 1-13. Another person in my company reported that after he deleted a number of contacts, they held empty spaces in the page scrolling area.
I tried to repeat process on another machine (filing by Company (lastname, firstname)) and got the same results twice and had it work once. I was changing the other fields that were entered and it seemed to work when I added the contact with C(l,f) and fail [delete] when I edited to C(l,f). Let me know if I can provide more information for you.
PS we have about 25,000 emails on the test system and the performance is still excellent! Great Work!