Thank you so far!

This is really the original url history database file that gets restored when you delete your browsing history. I was able to change the entries in the original db and the changes were reflected.

Then there is just the styling feature left. Regarding this I've found out that the styling is linked to the entry's ID.

For example I found out that the ID 1 and 7 are linked with the styling for "Latest on Nokia N9", 2 and 8 with "Nokia N9 Features", 3 and 9 with "Nokia Environment", 4 and 10 with "Nokia Support", 5 and 11 with "Nokia Conversations", 6 and 12 with "Nokia.mobi". Anything above 12 seems to be links with an empty (or maybe just a non-existing) styling because these bookmarks will be displayed as an empty entry provided the hasIcon field is set to True.

So I guess there may be another database (hopefully - it could also just be hard-wired) where these stylings are stored (I guess they consist of plain HTML).
So now we just have to search this database... I'll try to find it but if someone else is also interested any help is appreciated.