Redirect ARE easy to delete. But allready with Wikipedias with under 50.000 articles you have some/many unexperienced admistrators who leave these links behind. Besides you said that leaving these redirects can be usefull. Can it? Is it realy good that when you click a link you get an article that is deleted (moving to user space is not an alternative to deletion, it is being done only for article that admin wants to delete, or articles that were voted for deletion).
You may be right... they aren't useful very often, and your point about inexperienced admins is a good one...