I use random encounters when traveling overland for long distances. In the civilized lands, a "monster" encounter is rare -- there are military patrols and hunters out keeping the main roads safe. In the borderlands, on the fringes of civilization, a monster encounter is possible, but unlikely -- less frequent patrols and hunters. In the wild lands, between civilizations, travelers better be prepared for trouble -- this is where adventurers are needed a lot. The bulette was encountered in the wild lands.
I don't have dragons and unique monsters on the random chart. The average EL of a random wilderness encounter (in the plains area, where the adventurers currently are traveling) is around 6.
The bulette is one of the most dangerous creatures on the random chart. The PCs know that harpies, animals and dire animals, cockatrices, and ankhegs are on the chart, too. But there are also giant owls, pegasus', and unicorns roaming the wilderness.
A group traveling in the wilderness either needs to be fairly strong (~6th level or higher), or able to conceal their presence from the less friendly critters stalking the land.
My main concern with this wasn't the random aspect, really. I tell the Players at the beginning of a campaign, the world exists as it does whether the PCs are 1st level or 20th level. The world does not scale with the PCs' levels.
If a 1st level group goes out into the wild lands, they either better work to avoid encounters, or go in very large numbers. If they are 20th level, they will have very little trouble with the monsters about.
Especially at the low-middle levels, the PCs need to realize random encounters are not created specially for them. They must know when to run and avoid an encounter. This is where my concern came from. The PCs determined that the bulette was an encounter they should try to avoid, and they worked to do so. But it kept coming. And I was worried, after the fact, that perhaps I forced the encounter on them, and possibly "taught" them that they *can't* avoid encounters.
Fortunately, for my conscience, the replies here have supported my play of the bulette. It seems the PCs just chose an ineffective way to avoid the encounter -- feeding the monster and rewarding its perseverance.
They have played smart in most of their wilderness encounters -- going out and meeting the threat away from the caravan. They even hired guards to stay close on the wagons specifically so they could be mobile around the caravan.
Quasqueton