Study, Study, Study
Information is really the only way to overcome this problem, and it comes in a few varieties:
Know Your Players - This one is the most important. You should familiarize yourself with the capabilities of the PCs and with the tactics they tend to favor. Do they search a room when they walk into it before they do anything else? Does the party wizard like to summon? What is a Factotum anyway? This is the single-most important consideration because it helps you to determine what kinds of monsters they might enjoy fighting, where the strengths and weaknesses of the PCs are, and most importantly how you can challenge them without automatically throwing their characters into the killing pit. An important distinction to make is that a player's character might be capable of doing something that they have not, to date, done. Plan for their current tactics, but keeping the capability in mind for later will help you adapt, and can also help you if you want to teach your player how to use it.
Know Your Monsters - This is a lot like knowing your players, except for monsters and NPCs. However, you have additional considerations - how intelligent is the monster? How wise? Can they cast spells, and how often? Does their entry list any preferred tactics, and are those tactics intelligent? If the monster is mindless, can it be directed by another monster that can give it orders? Pre-built monsters are rarely designed in an optimal fashion, but you can increase or decrease their power level by changing around even such small things as the items, feats, or skills the monster is trained in.
A very important consideration is to look at how intelligent a monster is. Let's take the Erinyes as a specific example of doing the above. The Erinyes is a CR 8 devil (an embodiment of Lawful Evil), which means that in theory four of these lovely ladies is an appropriate boss fight for a level 8 party. The first place I look when deciding how to characterize this monster is her alignment (Lawful Evil) and then her ability scores, which are listed as "Str 21, Dex 21, Con 21, Int 14, Wis 18, Cha 20". What this tells me is that, compared to humans, the Erinyes is unnaturally strong, quick, and tough. That 14 intelligence indicates that they're smart and cunning but not genius-level intellects like a wizard, but her exceptional Wisdom means that she's perceptive, quick on the uptake, and aware of her environment, while her 20 charisma speaks of unbreakable self-confidence, self-assurance, and a strong self-identity (which, since she's Lawful, might indicate discipline, restraint, and a sense of patriotic pride in Hell). So right there we can reasonably say that this monster is going to try and use effective tactics, take full advantage of her natural and supernatural abilities, and come at the party from odd angles.
Little Details - Relating to the above, you want to familiarize yourself with some of 3.5's terminology so you can know it at a glance. Keeping with Erinyes, above, we can see that she's an "Outsider [Extraplanar, Evil, Lawful]", which while it doesn't have further explanation in the entry causes her to be strong - or weak! - against a variety of spells and abilities all by itself. If it helps, print out pages or cards explaining what the abilities of a monster do before you run an encounter with it. Look at how a monster might use their abilities in a synergistic fashion and spend their entire turn doing stuff instead of just part of their turn. A great example for this Erinyes is combining her power to fly and her longbow, or her at-will Unholy Blight ability, which puts her out of the range of non-ranged attackers and lets her rain down death with impunity. She's immune to fire, so perhaps she might use her flaming arrows to burn the building the PCs are fighting in, or confront them in the midst of a blazing wildfire, trusting in her fiendish nature to protect her while they're forced to spend resources avoiding the flames.
Of help in these considerations is the System Reference Document, and specifically the Types and Subtypes, Special Abilities Descriptions and Spells section.
The PCs Don't Have to Kill It - A lot of monsters and spellcasters have unparalleled ability to run away. Whether it's an Erinyes teleporting to safety, a worm-like creature burrowing away or a sorcerer invoking a flight spell to escape combat, most villains and monsters don't want to stick around to be killed by adventurers. This doesn't have to be a bad thing - not only does it potentially give you a recurring villain, but the XP system in 3.5 rewards players for overcoming challenges, not for killing monsters. If they make the fiend flee, then they're overcome the challenge. Additionally, the ability to teleport to regroup can make for a more extended encounter as the PCs deal with recurring harassment by a determined enemy until or unless they can pin it down and force the end of the battle.
Another interesting option for this is the monster or NPC surrendering. Aside from letting players with certain concepts (like a bounty hunter, or a merciful paladin) indulge in the ability to turn an evildoer over to justice or help them on the path to redemption, this can be a way to further the story. A great example is in the module Expedition to Undermountain, where the players encounter a Mimic. If they defeat it, it surrenders and begs for its life, offering to report on the activities of people that pass through its hallway in exchange for food. In this fashion a monster or NPC still gives XP to the player characters, but also can become a long-term ally (even if it's a difficult ally) or a beloved companion.
3.5 Has No Aggro Mechanic - This one is the biggest source of people wondering why a supposedly strong monster is weak. A common misconception people have about 3.5 is that, like World of Warcraft or Everquest, the guy wearing armor is automatically a more appealing target. Nothing could possibly be less true, especially for an intelligent monster. Why should a flying monster stay toe to toe with the fighter (and get cut to ribbons for the trouble) when she could fly, ignore him, and take out the dangerous sorcerer? There's no mechanic that lets fighters or other melee types "hold aggro", which means that an intelligent monster will assess threats based on what's happening, their own experiences, and their Knowledge ranks. Demons and devils, for example, will go after clerics and wizards because they know those dangerous beings can banish them back to the Lower Planes, while the sapient-but-sorta-stupid orc might prioritize a fighter or cleric first out of a desire to fight a great warrior. In most cases, however, a monster or NPC will target whoever is making themselves the biggest problem, so if a melee concept wants to hold down aggro they need a reason to make monsters care about them or a way to control the battlefield enough that the monster must needs go through them to get anywhere.
And, finally, Even Smart Monsters Can Be Stupid - Yes, part of the point of this guide is to encourage DMs to play intelligent monsters up to their potential, which can lead to more tactically interesting games. However, D&D is also a roleplaying experience, which means that personality is part of it. Yes, the Erinyes is incredibly clever - but she's also incredibly Lawful and incredibly Evil, which means that she might be operating under oaths of service that restrict her, or that she might get sloppy in an undercover operation because she took the chance to torture a homeless man to death instead of covering her tracks. Unless your game is high-optimization (in which case, by all means, pull out every stop you have) these sorts of little mistakes both help slate the odds towards the PCs and help flesh out the personality of the monster so that they're not just a generic being.
Best Answer
It's likely case by case and influenced by lore. You can probably find examples failing your test on either end, but it seems a good starting point. But honestly, I'd just run it case by case, as situations come up where a player wants to influence an actual creature in your game.
Let's take some examples:
Ogres are Int 5 and know a language; by your criteria they would be pets. Most people would consider them sapient (if barely).
Trolls are Int 7 and know a language; they would be sapient by your criteria and most people would agree.
Worgs are Int 7 and know multiple languages. They are described as being "mounts", but are also known to turn on their riders if mistreated.
Likewise, Winter Wolves have Int 7 and know multiple languages. They are described as being "companions", which probably makes them sentient.
Your Pseudodragon example has Int 10 and understands languages, but can't speak. It seems that its ability to communicate is limited only by its body, not its mind. They seem to make a conscious choice to bond with people and do not accept poor treatment. I'd say that makes them pretty sapient.
Remorazes have Int 4 and don't know languages. According to their description, they can be trained to become guards.
But then, Ropers have Int 7, also don't know languages. They do not appear to be trainable at all. Whether they are sapient is unknown, but they certainly seem smart enough to be.
Scarecrows have Int 10, understand languages, also don't speak. These things are "bound to their master's will", so despite pretty high intelligence, they probably aren't particularly sapient and they can be "trained" in so far as they do what their master tells them to.
But then Helmed Horrors also have Int 10 and understand languages (but don't speak). But they are clearly described as being "intelligent" and "loyal" and can interpret your orders and act on your intentions. They also devise tactics. So clearly they are some form of sapient.
So it seems that neither having (or not having) a language or having an Intelligence of 5 or more is a clear indicator of something being sapient. Some creature types seem more likely to be sapient (ie; humanoids, giants, dragons) while other less so (constructs, beasts, undead) but there is probably counter examples within each type.