Okay, I've been doing a bit of thinking on how the Tarrasque is supposed to be some ultimate engine of destruction. Except...it's really not. I mean, sure, it's dangerous, but it really shouldn't be that hard to track down and kill. Here's why.

First off, the big T can't teleport, planeshift, or do anything else that would make it impossible to locate the thing's lair.
Second, the Tarrasque is big. Very big. That means it's obvious, especially considering its tendency toward eating everything in its path. It would be relatively easy to find out where the Tarrasque has been, just piecing together info from rumors and legends.
Third, the Tarrasque spends most of its time sleeping in its lair.
Fourth, it's slow. Even assuming it uses its Rush ability as often as possible and doesn't stop or slow down for anything, it can still only move at 330 feet/minute. Its normal waking time is 1d3 days. That means that at most, the furthest the Tarrasque can go in one cycle is *does some math* 11.25 miles. Now keep in mind that it needs to go back to its lair to sleep. 11.25/2=5.625 miles maximum distance from its lair. This, of course, assumes that it always stays awake for the maximum length, and that it moves at maximum speed the whole time.

Now, to find the big T, all you have to do is find the last place it was seen, and then work outward from there. You have at minimum 6 months to search an area of at most 100 square miles to find something the size of a five-story building. As for major cover? Forget it. Anything that would hide it, like trees, large rocks, etc, would have been eaten on one of Tarrasque's feeding frenzies. It'll probably be, at worst, gentle scrub and hills.

This should make finding the Tarrasque's lair fairly simple. And when you find it, it'll be sleeping. As for killing it, well, there have been numerous ways suggested to go about doing that, so I won't bother talking about it. Suffice to say that it should get far easier when you can take the fight to it.