I think Pidgeot needs additional cards to do well or something to give it more HP so it can tank hits. It still does well against decks that trade hits with it but if it come across a deck that can OHKO it, you just lose and your Max Potions just become dead cards, which makes it harder to use Octillery since they just sit in your hand. I don't think other cards can really work with it but I'm still looking for other options but I think each card option needs to let Pidgeot do what it wants to do better so no useless tech. I think the biggest problem facing Pidgeot EX and its mega is the fact it doesn't have enough HP.
I have started brewing with M Pidgeot EX and found I often mega evolve the first active one without a spirit link as I was not going to attack anyway. Your comment had me thinking if I could have attached an Assualt Vest then it would effectively have 260 HP vs anything with special energy, i.e. the things that most likely ohko it. Just an idea.
Secondly I have been using 2-2 Umbreon GX line alone side it, early strafes allow you to switch into a Pidgeot while still doing some chip damage. The GX attack gives the deck an GX option as well as some disruption and the Shadow Bullet 90 dmg attack plus 130 from Mach Cyclone does 220 dmg when combined. Also redundancy in Shadow Bullet and Feather Lance allow you this to be a viable strategy as well. Effectively both primary attackers have 3 attacks when Shrine of Memories in play, Umbreon technically has 4 if you include the one it gets from Eevee SM. This is what I just threw together, but it is very untuned and the trainers are definitely a mess up, I was not playing Puzzle of Time.
Would you mind posting your list to see what the puzzle of time and supporter/trainer packages look like?