Not that you should have to, but web results can be disabled in start search.

Winkey+R will open the no-frills run menu. As long as you know the exact exe or component name, you're good:

• notepad
• calc
• cmd
• control
• control userpasswords2
• mstsc
• ncpa.cpl
• diskmgmt.msc
• devmgmt.msc
• shutdown (with /s, /r or /h switches)

A few decent ones there.