From what I understand, when you delete a file on your computer it isn't actually erased. Instead directory addresses are rewritten so that for all intents and purposes the files are gone. This is also true about formatting, the main directory is reset to show all clear. Only when an erased file has been overwritten is it gone for real. Using a program such as
PC Inspector File Recovery enables you to recover lost or deleted files. Not sure if it will work on internet history though.
If you click
here it will take you to a site where you can download it for free.