I reverse engineered a flash application that showed a map and provided address search. I scraped the map tiles and address to location database. Reimplemented the viewer application as a Java applet and preloaded the tiles and address database to a microSD card connected to the phone. So essentially I built my own offline maps for my not internet connected phone.
Address search required prefix tree because IO was too slow to use binary search on the phone.
Anyway this was done just before I went to a new city to attend university and it was really helpful to find out where I am and where to go. There was no navigation, but it showed the map, gps location and the location where I needed to get to.
So that was my personal project that really had great utility for me.