Even with stall decks/lock/milling decks i have never had a problem with (my) time. at most i could take 30 minutes.
however i have had a battle last over 2 hours (obviously not timed) because the person i was battling took 10 minute turns. then i could do what i need in less than a minute, then i would wait for another 10 minutes. (i don't play with that person anymore)
it depends on the players. if both players know what they are doing and have a plan and can adapt then it should be enough time.
however i have seen people use time to their advantage, especialy when they know their opponent runs a deck that needs the full 25 minutes. I can see someone who knows you are running a lock deck humming and hawing at setting their first pokemon out, examining their hand, nothing outrageous, but enough to run the timer down.
with less time in a match that could allow people to take advantage of cheap wins this way.
And well yes there are people who just can't make up their mind, or want to double check, im not saying they don't exist.
I do not believe it should effect the deck, but it could.