Okay, I started using an Adamant Mega Beedrill with 31 IV in both Attack and Speed, and 252 Attack and 252 Speed. I run Protect the first turn so my Beedrill's base 75 Speed won't matter. Now, I battled a friend several times, and his Modest Greninja with 252 Speed EVs and Life Orb (base Speed 122) and Adamant Mega Kangaskhan with 252 Speed EVs (base Speed 100) as well was able to outspeed my Mega Beedrill even after the first turn. How can that be? Obviously there're no Scarfs, or Quick Claw or anything; no Tailwind or no one Baton Passed Agility to them. Yet they outsped my 145 Speed, fully invested. Hoooooow? :(
You have said there was no Tailwind, and that you used Protect.
Did you forget to use Protect?
Was Tailwind put up and you didn't notice?
Had your Beedrills speed been decreased from Sticky Web?
Are you sure on the EVs?
Are you sure they didn't receive a boost from Baton Pass?
These are the only scenarios I can think of, as max Speed Beedrill will always outspeed the Pokemon you mentioned. Do you have access to the battle video? That would help a lot.
Hope I helped