I believe this is still an issue. I have tried most of the suggestions here. Some seem to work (sometimes), other times they are not effective. It's hit or miss. Maybe it occurs after a certain combination of removing/re-sharing/saving/etc. The redesign of the Open Data Portal editor added an "Update Index" button (under Data Reports) to identify broken feature services, etc. but does not seem to work properly, as the services I had removed still show up in the portal.
If anyone out there has another solution or idea, let me know.