I like very much the Maps.me and I have recomanded it to several people.
I would like to know if it's possible to search in London by the postcode or how could I add myself the postcode database (into to my phone).
Postcode centroids have been freely available since 2010. freethepostcode was set up before then (as was npemap, a similar site I was involved with: http://www.npemap.org.uk/FAQ.html#whatIsIt ).
Postcode boundaries, however, are still not available openly.
I wonder how much absolute error there is between the actual boundary and a Voronoi boundary. While I'm sure there's some massive IV postcode for which it wouldn't work, if most postcodes are tiny, then the fact that you're off by under a kilometre isn't so bad for routing.
Maps.me now lets you edit OpenStreetMap directly, so you should be able to add your own postcode directly. I don't know what kind of UI they've added, this can get kind of deep, but nothing that someone reading HN can't figure out.
[0]http://www.freethepostcode.org/