Having a 25 star deck depends on what mode you play in.
Classic has no restrictions, you use any card you want, but I've seen that I tend to get paired against opponents that have similar starred decks.
Deathmatch has Extended, Standard, and Extended 25.
Extended is what classic has, use any card you wish.
Extended 25 is any card with a limit to 25 stars, what you say you prefer to play with.
Standard is cards among the more recent releases, I forget how far back exactly they go, but it just takes out a handful of the original cards, with the exceptions of Ld's, Leaders, and starter cards.
Elo format is Extended, however there's a lengthy list of cards banned, with some changed every week or so. There's other small restrictions, such as no developing cards (
Charlie can be used as an excellent 4* for example, but you won't see it in ELO)
Survivor has Extended (T2) and Type
ELO.
Daily Tournaments are split into 3 levels, 0-23 stars, 24-31 stars, and 32+ stars, however you can win up to 5 bonus points each match for winning against a higher star deck (1 point for every star, if you have 24 stars and they have 27, you'll receive 3 bonus points.)
If you prefer the old format, extended 25 and type
elo are your best bets.
Sometimes when someone's in a game mode and changes deck while they're in, they aren't kicked and could end up using a 34* deck against your 25* unintentionally.