Recently Spotlight stopped offering me Bing results (or Wikipedia). Power cycling the phone didn’t help. I tried the usual Spotlight fix in Settings:General:Spotlight of turning off all search results, exiting settings, confirming searches return nothing, then turning them back on. Didn’t work this time.
After a bit of experimentation I found Spotlight worked as long as I didn’t include mail search. Not unexpectedly, when I tried searching within Mail.app search would hang for at least 30 seconds (when I gave up).
The fix was to remove all of my email accounts entirely - it wasn’t enough to simply turn mail off. I then restored them  and now search works within Mail.app and also within the Spotlight UI — including Bing results.
I assume Spotlight performs searches in sets, and when it got to the set containing Mail it got hung up, returning nothing and blocking returns from later sets in the execution pipeline.
I decided I don’t like getting Mail results back in search anyway, so I turned them off. I do like being able to search Mail, so the fix was important.
My spotlight enabled searches are, in order:
- Events (I use Calendars 5.app primarily, but I enabled Google Calendars in Calendar.app to support Event search. Sadly iOS still needs Google’s ugly SyncSelect hack. OS X doesn’t need it, so I blame this one on Apple and their (assumed) monstrous technical debt problem.)
- Spotlight Suggestions
- Bing Web Results (also Wikipedia)
I only use iOS Reminders for short term things (use ToDo.app) so I omitted that. Similarly I only use iOS Notes for transient items, so I omit that too (use Simplenote.app, despite it’s #$@$@ tag limitations). Messages, Voice Memos, Music, Podcasts, Videos and Audiobooks never made sense to me as items to include in Spotlight search.
 I had to redo my settings of course, including digging into preferences to make Google Delete when it damned well should Delete. I set it only save the last two weeks of email to reduce burden on the evidently unreliable indexing engine.