As for the Run MRU have a look at:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\RunMRU
Document MRU is saved on filesystem as .lnk-files. Under Windows 7 it is:
%APPDATA%\Microsoft\Windows\Recent
Edit:
On this XP Machine I've got only one entry under the key
HKEY_CURRENT_USER\Software\Microsoft\Search Assistant\ACMru\5603
It is
Name=000, Type=REG_SZ, Value="*.tmp"
I suppose that means that on this machine Search has only been used once, more precisely it is the first (and only) entry in the MRU list, so next entry showing up would be:
Name=001, Type=REG_SZ, Value=...
and so on.
If your question is now how to access the Windows registry, have a look here:
http://stackoverflow.com/questions/1880275/good-windows-registry-wrapper-for-c
or for the plain api here:
http://www.aspfree.com/c/a/Windows-Scripting/Working-with-the-Windows-Registry-in-C-plus-plus/