First you need to create a new playlist by selecting 'New Playlist' when you right click in the left pane in iTunes. Call this 'All Files'. After you created this playlist, drag all of your songs into it. This means all songs in all other playlists. This can take a bit of time for iTunes to process, especially on large collections. Hint: you can select all songs in a playlist and drag them together.
After you created the first playlist, it's time to create a second one. This time you want to select 'New Smart Playlist'. Call this one 'Missing Files'. Use the settings as in the picture below when creating this playlist.
The 'Missing Files' playlist will now contain all of the files that iTunes can't find. So click that playlist, select all songs inside it, right click and delete!
You will be asked to confirm whether you want to delete files or not. There's no going back if you click Delete now, but since all the files are missing anyway it should not be a problem.
This article was inspired by: Quick Tip: Remove All Missing Songs from iTunes.