OVH pre-install a number of things by default on their Debian image including monitoring software (it integrates into their manager) and this key.
The only way to make sure things like this are a non-issue is to do a clean install yourself, e.g., via debootstrap in "rescue pro mode".
You can then install the key on their request if required giving you more control.
We are aware of this and are currently investigating it. Our initial thoughts were that it was indeed a compromise but after further review it seems that this is actually a bug with Debian and certain versions of RedHat.
We've tested it with different keys and have suffered the same results. I'll let you know if anything changes and we'll be announcing this shortly.
Thank you in any case, but rest assured it's not a serious issue.
However, I have grown a great distaste to them in the last few years, namely because of this behaviour and it's implications; when I buy a dedicated server that I am going to manage myself it would be nice to at least have the option to install a clean distribution and not have to go the extra mile of bootstraping.
They have much worse things in place:- their anti-dos measures make it near impossible to put anything of value on their without a LOT of work. For example, once they detect a DoS (just 50 Mbps was enough but it varies) they will take down your server (not just its IP) for 4-12 hours at a time.
With that said, there are some great things about OVH: they drive down the costs and make everything quite efficient (e.g., hardware prices, support costs) but then seem to just forget that they need to reduce the costs for the customer as well (their anti-dos measures being an example of how they increase the cost).
I believe (not 100% sure) they put their anti-dos on these routers which is why I think the US servers will have the same anti-dos measures.
Have you tried asking them? I do not believe they would hide this fact (it would be interesting to know whether they mark it as a selling point or not).