Ah, ok. Test something else: start Internet Explorer, and look into IEs history. Even IE will show you a "clean list", without the deleted entries, so these entries have been removed from IEs perspective.
What you see in the Local Settings\History folder is a complicated thing. Those are not regular files - this folder is actually empty except for a desktop.ini, which names two class IDs responsible for displaying what is seen there (that way, every folder on a hard disk could be used to display stuff that's totally unrelated to the files there). UICLSID is responsible for "Temporary Internet Files" in general, CLSID is responsible for the "History". Both are pointing to ieframe.dll.
Now I would expect that this explorer folder handlers would enumerate history the same way Internet Explorer itself (and BrowserCI, Spybot-S&D, ...) does - but it seems it doesn't, taking the information from another place instead. Since the only file that contains links is the known index.dat, it might be that the explorer folder handler does ignore any delete-entry flags inside index.dat.
So, to sum things up: not only the Spybot GUI or BrowserCI, but also Internet Explorer, the target of the operation, shows it as cleaned. That there still is some history visible through another way probably validates another, new detection entry.
BTW: DeleteUrlCacheEntry is the function to use to remove something from many an IE related list (history and cookies for example are just cache entries there). Note the description "Removes the file associated with the source name from the cache, if the file exists." which sounds like it would actually do get rid of everything.