Mega Beedrill tops at 427, whereas by your own calcs Agility Empoleon is 438, so it will outspeed, unless M-Beedrill has positive speed modifiers.
As for the Heliolisk, sumwun is absolutely right, it must have been Scarfed which gives it a whopping 522 speed.
Scarfed Heliolisk is uncommon, but not rare, so it is very probable you ran into one. (Life Orb, Specs and Scarf are the most used, imo). This is specifically to counter the fast but frail Pokemon and OHKO them (mostly to revenge kill)