We already do local bookmark backup, and use KML natively I think. It just doesn't sync, resolving sync conflicts is hard.

Not really. I imagine a sqlite db, but I haven't thought about any particular schema.