I think the problem isn't so much "where you start", but rather if you stop and backtrack along the way. What I mean is that if you have "convoluted interfaces, unused class/struct/type member variables, duplicate data" etc. then you started with some approach but never stopped for a minute along the way to redesign things using the knowledge you've learned from the first implementation pass.

I sometimes end up with a messy and crappy solution on my first try, but it does work (sort-of) and then I just start from scratch again, liberally copying stuff over but also deleting/changing a lot of stuff, as needed.