IE 5.5 Auto-complete URL Issue

I have a client who has some URL’s “stored” somehow so that they always show up when he starts to type in the address field in IE 5.5.

I have tried deleting the auto-complete cache, the temporary Internet files and the history. None of these actions has any effect on these URL’s. I have searched the registry and searched for files containing this text, but it has been fruitless.

What is going on here? Where are these things stored and how can we get rid of them?