What method are you using to delete files on the phone? I watched a movie on my Captivate yesterday and I just deleted it a minute ago after reading your post. Media Scanner ran automatically after the "delete" operation finished, and the movie no longer shows up in the Video Player.
The steps I used:
1. Open the stock "My Files" app.
2. Navigate to the directory with the movie.
3. Long press on the file name, click "Delete" from the pop-up menu.
4. Media Scanner ran automatically.
5. Open the stock "Video Player" app, which said, "Your phone does not have any media files".
As far as your browser issue goes, what do you mean, "it's still there"? What is still where? =) Cookies? History? Something else? I just opened my browser, clicked "Menu | More | Settings", scrolled down to "Privacy Settings" and clicked every item that had "Clear ..." in front of it. I also clicked the one under "Security Settings" a bit further down. The browser seems to have properly cleared everything: no History, no cookies, nothing.
If you can give us some more information on what, exactly, seems to be wrong, we can try to recreate your issues locally. Also, are you using the stock, unrooted Captivate ROM, or have you rooted and installed something else?