Quite possibly most people are the same… Did you get a feeling that support knew how to answer the question, for example did they say what key you should be expecting? Is this a public hosting provider? Commonly I could see how support people are not the experts who actually administer the SSH server.
So the first idea is maybe support did a search of their documents, and passed out an outdated answer.
Man-in-the-middle attack is another possibility, but if you’re inside a company that values security or has strict employee Internet access policies, companies will sometimes monitor their traffic with the Internet.
Lies, Damn Lies, and Inspecting SSH Traffic Securely talks about how security gateways might monitor, however don’t assume that such interception is legitimate, especially if you’re not in a company situation.
Man-in-the-Middle (MITM) Attacks gives technical details on “could be the reason”. For questions that are “generic” in nature, you will probably do better using an Internet search than asking on this limited forum.
Duplicate SSH Keys Everywhere is interesting. Your key appeared 4393 times on the Internet, and trying
https://www.shodan.io/search?query=90:E0:66:4F:F5:24:30:B4:72:BC:4B:67:90:88:DA:43 shows that most of them are SingleHop OpenSSH. The numbers are a bit lower, but maybe they put up many servers configured as a pool, so that customers could access any one without a fingerprint alert?
The SSH Key Problem With Cloned Linux VM’s might be a more likely answer if the shared host is your private IP addresss to ssh to directly. The article explains how the IP may be private, but the key shared.