If you are comparing Mega Aero with Deo-D you are certainly using a wrong set. Mega Aero shouldn't be setting up hazards or dicking around with Taunt (which is an ok option though), it should just aim to as best at revenge killing as possible, which is its best role. I want you to mention one common unboosted speedy offensive threat that Mega Aero can't outspeed and OHKO. His offensive options are terrible? How is that true when it has very strong coverage moves such as Aqua Tail, Earthquake, Ice Fang, Aerial Ace, and Fire Fang, all of which except from EQ which are boosted by its ability. Mega Aero is basically the ultimate revenge killer against Pokemon that don't boost their Speed. It is even able to take one hit from common late-game sweepers with priority, such as Talonflame, Mega Lucario, and Mega Pinsir, and OHKO back. And it's not even easy to wall, as only dedicated walls such as Hippowdon and Skarmory can wall it, which only need to have taken a little bit of previous damage to be 2HKOed by the appropriate coverage move btw, or just lose if Mega Aero packs Taunt.For exactly the reasons you just mentioned, Mega Aerodactyl is almost certainly better off in C or C-. The utility set you mentioned is almost completely outclassed by Deoxys-S who has:
-more speed
-Stealth rock AND Spikes
-Faster taunt
-Recover (if you really think recovery is helpful on such an obviously suicidal set)
-An even diverser offensive movepool (diverser is totally a word no matter what spell check says) containing ice beam, thunderbolt, superpower, fire punch, psycho boost, and probably a ton of other things I'm forgetting.
-Can use a focus sash
-Also doesn't take up a mega slot
As you mentioned, his offensive options are also kind of terrible. So yeah, outclassed and not that good to start with > C.
I don't really have a good ranking suggestion for Mega Aero atm, but its disturbing to see how people misuse it and misjudge it.