In this particular case I would use some Quickcheck-like generative test library and give it a description of how to generate random dates (i.e. start by generating a day, then a month, then a combination of both etc) and then leave to it the generation of all test data.

The amount of edge cases Quickcheck catches is beyond the most comprehensove unit test suite.

On a higher level though I would use parser combinators. If you have a grammar specification you can then directly transform it into a parser and thus would only need to test that you transformed it correctly (i.e. prove the proof as opposed to prove the implementation if that makes sense).

Basically - try to capture most of your invariants in the types and then you know your code is correct. The invariants may be wrong though, in which case integration testing may help.

However, I still have no idea how to test programs with complex state and IO in a way that isn't basically "script the 5 behaviors I can come up with and pray for the best", in which case I mostly don't even bother (i.e. UI etc...)

(I know this is a very short answer but I'm typing on a phone)

You can make a finite state machine to model your expectations on random input, but then your test code is almost as complex as the code :) I've found quickcheck super useful as a way to fuzz user input or find edge cases in unit tests I didn't see, but I still write all my integration tests by hand because they are so hard to formalize.