The giant worms in the Earthgift Shrine are Abyss Worms. The difficulty there is that they are about as rare as Warmech, they are only slightly weaker, and Warmech is worth 8 times as much experience. Warmech probably is the most powerful random encounter in the game, it's just the rarity that makes them tedious.