Software estimation is only hard when you don't understand what you have to do or how it will be done.
Just keep breaking the problem down into sub units that you or your team understand and can fairly accurately understand the effort and risk of (because they've been done before)
If you already know how to write it, why haven't you automated it? One could say, the worst developers are the best in estimating their tasks, because they repeat everything they do all the time. ;)
At some point you probably will want to do a rewrite. I don't think it is surprising that this sort of analytical process of bite-sized task creation also uncovers architectural deficits in your design.
That's the secret though, isn't it? The more likely you are to know all the steps the more likely you're going to make an accurate estimate. The catch there though is that if you know how you're going to do everything, you're already at least halfway through development.
Just keep breaking the problem down into sub units that you or your team understand and can fairly accurately understand the effort and risk of (because they've been done before)