We tear down and recreate the test database between different test programs. On the current test setup we're using, here's the timing information for our test suite:

While that's certainly not as fast as some folks would like it, we tend to run individual test programs and when we're done with a particular feature, bug fix, whatever, we run the entire test suite. Previously we used other methods (rollback, mock database handles, manually deleting information, etc.), between test programs, but we ran into so many weird edge cases that going ahead and dropping and recreating the test database was far and away a huge win for us.

Heck, even if a test died catastrophically halfway through and the test database didn't get dropped, the next test program still issues a drop command before trying to create a database, thus ensuring that we never have to worry about data spilling over between tests. It's also trivial to temporarily disable the drop on destroy command just to see if any test scripts aren't cleaning up properly, as that can often hint at bugs in code.

Update: I should also mention that Test::Class can also speed things up quite a bit in many area. With Test::Class, if you have 30 test classes, you're still only loading the Perl interpreter once, related modules are usually only loaded once, and many test suites can speed up quite a bit if you have slow loading code. Of course, the test organization and inherited tests also great. Test::Class still needs some work, but it's pretty damned good.