The toolbar was by Attracta, and I could not work out where the hell it was coming from. I had installed no new plugins (its a Wordpress site), but I had changed the template a little, so I instantly thought I had somehow triggered this.
I spent a good hour or more checking through my FTP folder to see if my theme editor had uploaded some new gimmick, checked that another plugin hadn't started causing it for some reason, and ended up totally stumped.
So I Googled it up, and discovered that this is some new SEO feature of Hostgator packages which is SUPPOSED to be optional, and needs to be switch on for it to work. For some reason it had automatically switched on for me, and it took a support ticket to stop it working, as simply disabling it in my cPanel didn't work.
So you might want to check your sites if you are using Hostgator, from what I can tell from search results its been a pretty widespread problem.