This appears to be an issue related to your physical location, because the two Eminem music videos that you mentioned in your question show in the search results of YouTube in my computer. You can verify this for yourself by installing Tor Browser Bundle and searching for the same two music videos in Tor browser.
From What is Tor Browser? at the official Tor website:
Tor Browser protects you by bouncing your communications around a distributed network of relays run by volunteers all around the world: it prevents somebody watching your Internet connection from learning what sites you visit, it prevents the sites you visit from learning your physical location, and it lets you access sites which are blocked.
Beyond this the question of why certain music videos are not uploaded to certain websites is primarily opinion-based, therefore it is not possible to answer this part of your question accurately.