We found it!
I'll tell you how, although I won't give too many spoilers for Sagiro's story hour. First, we're hunting for the tower - or, more specifically, something in the tower. If everyone had died off and left it for us we would be okay with that. Heh.
We had a few things to our advantage, and a few disadvantages as well. For one thing, the space we were hunting in was smaller than we originally feared, about 250 miles on a side - so only 62,500 square miles.

It wasn't completely uninhabited, either, being populated by what appears to be a race of something resembling stone giants. Thus, the concept of the largest humanoid waste dump became a lot less viable. Finally, Sagiro knew the limits and capabilities of the anti-divination magic, so he'd know if we managed to sneak around it.
We traveled via
wind walk and polymorph for about four or five days, hiding in
rope tricks at night and generally staying out of sight. Once we got to roughly the center of the area and survived an encounter with the
worst. wildlife. ever., we tried a few
find the path spells. The first one (which mentioned the tower by name) was throttled off by their anti-divination magic immediately. The second one was a little cleverer, but we weren't powerful enought to break through the spells; it, too, shut off immediately. When it did, we slapped a
nondetection on the spellcaster and changed location. At this point, we were considering knitting this really long rope....
But one of our wizards had a brainstorm. One of our enemies had once sent us a false vision of this tower while he was toying with us mentally. Thus, our next
find the path was something like "find the location which corresponds with actual location of where that vision represented." A little complicated, but sufficiently obscure so as to not trigger the tower's defenses, and the
find the path jerked into life. It failed a few minutes later as the tower's secondary defenses figured out that something had latched onto it, but by then we had the trail.
Good thing, too; the sage who told us it was an invisible tower bigger on the inside than the outside was apparently wrong. The place is smack-dab inside of a stone giant village, guarded by them - and it's a giant statue of a stone beholder.
Oh,
that bodes well.
Thanks again, everyone! We never tried the bird bones - just as well, considering the circumstances - but I still love the idea.