Я не знаю, есть ли API для этого, но если вы выполняете поиск в Windows для маловероятной строки, скажем «zxcvbnm», то ищите ее в реестре, а затем в XP вы можете увидеть ее под одной из папки в:
HKEY_CURRENT_USER\Software\Microsoft\Search\ACMru
вместе с остальными вашими последними строками поиска. Я предполагаю, что это местоположение реестра может меняться между версиями Windows.
Если вы нацелены на Windows 7, тогда эта статья MSDN выглядит хорошей отправной точкой.