Looks like Windows Search won't search through a directory junction or symbolic link:
Make windows search follow a directory junction or a symbolic link - Microsoft Answers
Go figure. One of the many reasons to dislike Windows 7.
I have my user profile folder on D:\
I have created a symbolic link which points C:\Users\ProfileName to D:\Users\ProfileName which means any request for C:\Users\ProfileName is seamlessly directed to the D drive.
If I open explorer to the root of D drive, search works fine, but if I try and search from "My Documents" or whatever, D:\Users\ProfileName won't be searched.
It's not a bug, it's a feature...