Web application testing is definitely a trouble area for testing fanatics, due to the issues you're describing.

I think the best practical advice I have for you is to use WWW::Mechanize. Each test script can model a certain type of common interaction, with test code for things like "load the home page", "follow the link that says Search", "fill in a query term and submit", and "does the current page have a link to the page we expect to find?"

If you were starting from scratch, and looking to build a more-testable web application, I might suggest the approach laid out in XP for Web Projects: structure the core of your web application to accept and return XML, and then use stylesheets to transform that into your HTML interface. That way, you can test your application logic using command-line XML tests, then test your stylesheets independently. (It also sets you up to support alternative interfaces such as automated web services.)