Re: The Amazon search results are still there
Try it in synaptic.
sudo apt-get install synaptic
Then search for amazon. Mark all packages, including the lens for complete removal. The Software Center only removes them, but keeps config files and at times doesn't really do more than disable them. In your case, something odd is going on.
Synaptic is a MUCH more powerful package manager. If you knew all the package names, you could remove them through the terminal. Be careful though, it might say you have to remove other packages when removing amazon packages. That's fine if it's ubuntu-desktop as this is only a meta-package that is useful for upgrading only... but make sure it doesn't remove anything important to you. Post what it says if this is true.
When your entire life is measured in one moment, you change the concept of time.