Spotlight Search on iPhone 4s doesn't show any results.
Everything is checked under Settings -> General -> Spotlight Search.
Restart doesn't help. New contacts don't appear.
Under Settings -> General -> Spotlight Search
are the areas you want to search selected (tick on the left hand side), if not just tap the group (Contacts, Applications, etc) to add them to Spotlight Search.
Found in a comment by "yigitcanakkas" here: http://www.youtube.com/watch?v=wfBSrZ1p2Tw
Whenever my search becomes unresponsive, my mail becomes unresponsive too. I open the mail and it's plain white, nothing happens, 5 seconds later it crashes, I open it again and it works this time. After that search becomes active again.