is it ok to manually remove menu_links entries from db? To my surprise, I removed one menu item from the main menu, and it correctly dissapeared from the admin ui, but there still is an entry in the table called menu_links. There is nothing unusual about the entry. How does drupal know it should not be used ? Can I manually remove it ? 

The problem is, I use custom code that traverses the menu_links table to generate an alternative menu. This custom code just sees the menu item and keeps on displaying it in the alternative menu. So, is that approach wrong ?
The menu_links table contains a lot of automatically generated rows. These come from the hook_menu() implementation of modules. Deleting these rows will likely result in them returning on the next time you clear the cache, because menus will be rebuilt than and the systems scans through all hook_menu() implementations adding new links.

If you look closely at the menu_links table, you'll notice there is a boolean field hidden. A value of 1 tells Drupal not to show this item in menu's.

So you can either filter out all hidden items (you only need hidden = 0 since the value -1 represents a menu callback), or you can have a look at the Drupal menu functions. There are a lot of functions with menu and tree, but if I am not mistaken you are looking for menu_build_tree.