Unlike regular files such as image, audio, video and text files, when you delete Bookmarks from IE, they do NOT go the the Recycle Bin, so you can't check there.
Using System Restore has been known to work in certain scenarios in the past, but if it didn't work for you, I'm not sure if anything else can be done in this situation.
As I mentioned above, it's a good idea to backup your bookmarks (also known as Favorites). When you backup your bookmarks, they will be compiled in one single file on your hard drive. That way, if something goes whacky with IE, you can always import your bookmarks backup.
To export the Favorites folder, follow these steps:
- In Internet Explorer, click Favorites, click the down-arrow next to Add to Favorites, and then click Import and Export.
- Click Export to a file, and then click Next.
- Click to select the Favorites check box, and then click Next.
- Select the Favorites folder that you want to export. If you want to export all Favorites, select the top level Favorites folder. Otherwise, select the individual folder that you want to export.
- Click Next. By default, Internet Explorer creates a Bookmark.htm file in your Documents folder. If you want to use a name other than Bookmark.htm, or if you want to store the exported Favorites in a folder other than the Documents folder, specify the new file and folder name.
- Click Next. If you already have a file that has the same name, Internet Explorer asks you to replace it. Click Yes to replace the file. Click No to provide a new file name.
- Click Export.
- Click Finish.