Well whadayaknow... I just tried again... still didn't work, but I let the search parameter "Abba" sit in the search window while I was Googling for a solution to this problem on my pc. After 10 minutes, all of a sudden, the files popped up! Now, all files can be found, just like it should be. Yay!

So my guess is the mac was still indexing the files or something. (shame there is no indication of it being busy with this task anywhere!) This is different from Windows. With Windows, even when a certain folder hasn't been indexed yet, it will still search, albeit a lot slower because it'll run past each and every file.

Oh well, it seems this problem had fixed itself. How often does something like that happen?