What do you see as the changes that forced the user to "re-learn the OS"?
In WinXP you might do: Start->Find folders and files. Write search terms. Location Dropdown->"Browse..."->Find folder. Press search.
Vista: Find the folder in Explorer, write your search terms in the search box in the upper right corner .
This workflow wasn't changed for a long time, as far as I remember.