Do you mean the links you see immediatly after clicking start. If this is the case you should be able to right click and choose "remove from this list".

If you start typing, it's actualy performing a search on your hdd and displaying real time results as you type. Sound like it's displaying links to files that have been deleted. Which means it's displaying cached results. You would need to clear the recent history.
Try clicking start, right click on recent items, click on Clear recent items list.
See if that fixes it.