I think this is a bug that Peter Bright at Ars Technica encountered. Apparently the Start Menu apps list is based on a database with a 512 entry limit. If you have more than 512 apps installed some won't be visible/searchable and uninstalling won't fix the problem. Apparently a fix from MS is coming soon.
These are known issues. New Skype apps are due out later this summer and I've seen rumours that MS will bring back placeholders in Onedrive soon.