I keep writing tests until I'm happy with the result of Devel::Cover, in covering all of the regular execution paths, and as many of the irregular paths as I can get at from outside the box.

And from there, I write a test for every bug I uncover that the earlier tests didn't show.

I'm pretty sure this strategy hits that sweet "80/20" spot, giving me the most return on investment.