And often if you box yourself into an API before you start implementing, it comes out worse.

I always learn a lot about the problem space once I start coding, and use that knowledge to refine the API of my system as I work.

Exactly, from my experience, most of the time (primarily when I need to do something new) I start writing code, when it starts working then I am starting to refractor it so it doesn't look like crap.

Perhaps TDD would make sense, when before any actual work starts, we would have POC phase to understand what needs to be done.