I was able to uninstall everything I wanted to.
You can certainly remove some of them manually or using 3rd party solutions but something eventually goes wrong specially after an update. I mean I can remove most of the executables from the Windows folder, my point is that it's going to break something eventually. Removing Cortana and SearchUI used to work before AU, now it just freezes my start menu completely.