Want to see what I'm talking about? Go here, and take a look at what it's showing: http://www.macromedia.com/support/.../settings_manager07.html
I'm betting there's a list of almost every single site you've browsed (if it was using some sort of reasonably advanced flash, or flash ads) in probably the past, oh, year or so, right?
That's where Flash stores its own, internal cookies.
Well, you have to take extra steps to get rid of these cookies from your computer -- you can delete them en masse, using that Flash app on Macromedia's site, but they'll keep coming back (yes, even if you set it to "never store this information").
A much easier way is to create you up a few batch files, with either of the following two lines inside them (works pretty much the same on either Windows or Linux):
// Ubuntu Linux
rm -rfv ~/.macromedia/Flash_Player/#SharedObjects
rm -rfv ~/.macromedia/Flash_Player/macromedia.com/support/flashplayer/sys
// Windows XP
rmdir /Q /S "%APPDATA%/Macromedia/Flash Player/macromedia.com/support/flashplayer/sys"
rmdir /Q /S "%APPDATA%/Macromedia/Flash Player/#SharedObjects"
And set them to run either when you start your computer up or when you shut it down.