The answer comes from a chat with Skype support...
This is part of the chat log. Slightly edited to improve spelling and grammar, but otherwise unchanged.
TLDR
When you click 'delete' in the Skype Web interface, the system actually just unlinks the Microsoft account. You now can't log into it again. With no remaining linked login systems, nobody else can log into it either. However the account itself is not removed through a cascading delete (although you would have thought that was a logical thing to do). It continues to exist indefinitely, and remains visible in the Skype directory if you search for it by username or email. You have to contact Skype support to get the'zombie' account totally removed.
Full excerpt of chat log
Support agent: "Creating a Skype account using your Microsoft account creates a system generated Skype ID that you can access using your Microsoft email and password. So it's like your Skype Tech account with the Tech ID uses your Microsoft email address as its backbone to be able to work and log in properly. Once you unlink the said account, the general term used is it will be 'deleted' since you are going to remove the said Microsoft email address from the Skype Tech ID; it's like you are removing the backbone of a person. [However, in reality] the body is still there but the backbone is gone (just for comparison). So now same with regular Skype account - in order to remove the account from the system it must be done by a Skype customer representative."
Me: "Ah right, so I effectively deleted the Microsoft account authentication link, which left a 'zombie' Skype account with no authentication mechanisms?"
Support agent: "Yes, just like a zombie"