At some point, wordpress is going to have to start releasing some of the older deleted names (at least when they aren't associated with an active username), but they haven't done that yet.
Yes, that should be done. Also, it would be great if something could be done about all these dead blogs. Besides sending e-mail reminders. There are so many abandoned blogs. Each of these that could be put to better use. And I don't mean blogs where the user has just stopped blogging (because lots of reasons like sickness), but those that have no posts....at all.
Perhaps something similar to hotmail, where if you don't sign in for a certain amount of time your account becomes inactive (later deleted I assume).