Did you save them using a particular application?
Here's why I ask: some applications have a default location for finding their stuff. And you, as a user, might not go to the Finder to find them, but use the application that created them. So you never remember where that application put them. Is that the case here?
I'm also suspecting that they are in one of the two Libraries (one is in your user folder, one is at the root of your boot drive). Check in both using a utility that can reveal hidden files. If they were hidden by the application that created them then Spotlight won't necessarily find them (there are more than one kind of hidden and/or invisible file and spollight doesn't index them all).
Finally, spotlight might still be rebuilding itself. I seem to recall it did so when I installed Lion. And that might be a reason why the files can't be found using a search.