Tests suffer from the same problem as code: they can have bugs. So they undergo the same development as the code they test, and it sounds to me as though you've done everything right:

First you tested the cases you could think of, and when you find a limitation in your approach, you expanded it.

1. When should I write tests?

When (or before) writing new features, and when you discover bugs.

What should I test?

The stuff you're working on.

Tests are a tool to achieve a goal (here: developing and maintaining reliable software), so they should be used to best achieve that goal. If you can't think of a way that your code would make a particular test fail, it's probably useless.

Tools like Devel::Cover can help you identify spots in your code that aren't covered, but you shouldn't blindly try to increase the coverage either.