I've had some weird things happen too when searching for files in a project using projectile, I fix it by triggering a refresh of the cache by prefixing with a C-u the C-c p f command.