Mac OS X has the annoying feature of remembering your application history in the dock and not erasing the history when you erase it from the application preferences.
The following is a little bash script that does this for you provided you pass the name of the application (e.g. vlc.app) to it.
#!/bin/bash -x BUNDLEID=$(defaults read "/Applications/$1/Contents/Info" CFBundleIdentifier) defaults delete "$BUNDLEID.LSSharedFileList" RecentDocuments defaults write "$BUNDLEID" NSRecentDocumentsLimit 0 defaults write "$BUNDLEID.LSSharedFileList" RecentDocuments -dict-add MaxAmount 0
You need to run
killall Dockafter this to restart the dock for the changes to take effect.