I have no choice but to use it since my laptop's hardware performs like crap on Windows 7. 8 = never as it forces me to use a Microsoft Account in order for me to sign in to OneDrive
I experienced this after applying some tweaks. After a restart or a shutdown the new tag keeps coming back. In the end, I never figured the service or a registry causing this. But I can definitely say, it has to do with the tweaks.
I'm pretty sure that what you are referring to has existed since XP as a registry setting typically referred to as highlight new applications. Try that Google thing and search for "Start_NotifyNewApps ". I've never tried it with Win 10, so not sure if it still works. The recently added apps setting just refers to a list of new apps that is shown at the top of the start menu.