Even though you shut off the auto complete, strangely enough I believe windows still catalogs recently visited urls under:
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\TypedURLs

now if there was a way to shut THAT off......