In Internet Explorer the Internet History and Typed URLs are stored separately. Typed URLs are stored in the system registry.
To clear Typed URLs try the following:
Go into Spybot > Mode > Advanced mode > Settings > File Sets. Check the last two Items (Usage Tracking and Tracks.uti) and run a scan (Check for problems). When the scan completes there should be a Green item listed "Internet explorer". Expand that item by clicking on the plus sign (+) in front of the item. Look for and check "Typed URL list" (there may be more than one if you have multiple users on the system). Then do a "Fix selected problems".
Note: If you want to do this quickly without going through an entire spyware scan, you can right click on the File Sets and choose "Usage tracks check only" and the check will be limited. If you do this however, you must remember to go back into Spybot > Settings > File Sets after the scan and check all the spyware checks again or right click and select "Select all available check" or "Spyware check only" (which is the default).