There are a lot of scripts available on a Mac to automate iTunes. One of the best resource is Doug’s Applescripts for iTunes web page: http://dougscripts.com/itunes/index.php but what if you are on Windows ?
There ain’t much but I found this page that contains the cleanup tool I was looking for : http://mysite.verizon.net/teridon/itunesscripts/index.html
Download the script-package and run the itunes_remove_notfound exe script. This will open a command-line window and will perform the clean up. On my NAS there were 3’ooo songs to remove and it took 15 mn.