As long as you haven't cleared the Bookmark Trash folder, all deleted bookmarks go into there for easy recovery . Go into Manage Bookmarks (Ctrl+Shift+B) and browse to the Trash folder to see your deleted bookmarks.
Just saw your post, a colleague had a similar issue and we found good troubleshooting info on the Opera site. They even have a page dedicated to lost bookmarks - http://www.opera.com/support/kb/view/378/, check it out, maybe you'll find a solution for your problem.
Rona
I do not fear computers, I fear the lack of them Isaac Asimov
I am terribly sorry I did not answer before now. I had trouble with my PC and when I got it going again, I had forgotten my questions! I just reviewed my notes and saw I had not answered you all.