Vista - Search doesn't return any results after adding location to Index

I have a separate HDD to which I make daily backups of my C drive. I wanted
to try out a couple things with the backups to which I needed all the ZIP
files that Backup & Restore has created.

I first selected the folder X:\<backup directory> in Windows Explorer and
then entered *.zip in the search box in the top right hand corner. All zip
files were listed. The search took a while because of the amount of backups
which have been done. Now, I wanted to try and make the search a bit quicker
if I had to do it again, so I clicked the small popup for "Searches might be
slow in non-indexed locations...". Now I can't find anything that resides in
X:\<backup directory>!

Searching in all other folders work normally on drive X (these are not
Indexed), so I decided to remove the indexing for X:\<backup directory>.
Didn't help, searching in the specific folder doesn't return any results, no
matter what.

What am I missing here?