The first version of TileMill was an utter failure. It was designed as an Amazon Machine Instance with Mapnik pre-installed: basically a rendering-machine-in-a-box. And so you would go into the Amazon Web Services console, which featured an absurd, abstruse user interface, boot up a machine, and then interact with it with a custom Python script written with the boto library.
It didn't work: when render jobs failed, there was sporadic and incomplete feedback. Most rendering jobs didn't justify the awkward client/server split. Users needed to be fluent in Python, Mapnik, Cascadenik, and Amazon Web Services to get it to work. But at that point, it was fiendishly difficult to just get Mapnik installed, so we thought it was a useful step up.
We rewrote TileMill with these lessons learned - aimed to make it accessible, installable, usable. It worked a lot better: a much simpler-to-the-user product but with many magnitudes more source behind it.
Of course, that path wasn't straight either: desktop TileMill was also written in Python with Cascadenik (with Tornado) and aimed to support multiple backends and even rendering servers on a different host, connected to with JSONP and so on.
Maps on a Stick might have been ahead of its time. For quite a while, I was lead on this project to support offline mapping. It was based on OpenLayers, our OpenLayers UI library called openlayers_plus, as well as big directories of tiles. It was pre-MBTiles.
And so the hard problem was copying millions of files onto USB drives. If this sounds easy, you haven't thought about it.
When MBTiles came around, Maps on a Stick became a portable server written in Python, packed with py2exe and the OSX version of that. No, Python multi-platform distribution tools do not make multi-platform distribution an easy problem.
Other notable failures were mostly internal - I tinkered on a realtime map-collaboration engine for quite a while (synchronized map views across browsers, drawing, snapshots, so on) before realizing that there was no one-sentence description of why it was useful, or how we could make it into a useful product.
You could say the same about some other projects which I can't really speak about. I won't comment on projecs that were not mainly my work.
Don't read this for cheesy takeaways: there is no way to avoid failure. But it's also not cool to fetishize it.
What is true probably:
Design for at least one user. Several versions of TileMill were designed just for AJ, our lead cartographer. Before we realized this, we were writing a map-design tool that wasn't used by the lead designer.
Respect the install. Distributing software is not an afterthought: it's hard to overstate the amount of time that went into making sure that TileMill would run on Windows, OSX, and Linux without people futzing with code. I made a mistake when I assumed that py2exe or similar would ease this burden. This is an unsolved problem, which no prepackaged software will simply 'fix' for you, regardless of what the advertising copy tells you.
Don't be afraid to reinvent the wheel. I'm guilty of warning others from reinventing wheels, but now think it's BS. MapBox's stuff includes a custom node.js framework, a reimplementation of a style language for Mapnik, custom Javascript libraries for interaction, even a new implementation of sqlite3 bindings for node. Most of these things already existed: there was already express, Cascadenik, OpenLayers, and so on. But they didn't fit. There is extreme value in components fitting in and keeping up. Don't confuse it with not-invented-here syndrome, but don't discount new wheels offhand: they might be better.
Demonstrate the art of the possible, others rarely see it. Most people are too busy to be creative. If there's anything we've done right with mapbox.js, it's having examples-heavy documentation.
It's amazing how far small time investments in innovation can go - MapBox made an OpenLayers theme in two days, and it will live forever. Every day I see a new site using it - and always the default coloring, despite the 10-minute possibility of customizing the colors in Inkscape. There are virtually no other options as far as OpenLayers themes. Maybe it's not that this is hard to do, but the benefit versus incremental cost is consistently underestimated.
The problem with premature optimization is bugs, not time. I previously had thought it was that optimizing things is hard and you're wasting your time. The reality is that naïve code that looks like it'll do the thing it does tends to have fewer bugs than code that tries to play nice with a virtual machine or a specific case or some bonus knowledge you happen to have.