praseodym is pointing out that there are two checkboxes called "Spotlight Suggestions". One in System Preferences, and one in Safari.

It's unclear which OP unchecked.

Screenshots of the two options: http://imgur.com/a/TWDxy

Had deleted my original comment because OP mentioned "all use of Spotlight Suggestions", so I assumed that OP did uncheck the Safari Preferences box. But apparently OP only unchecked the System Preferences one.

As noticed elsewhere in this HN thread (https://hackertimes.com/item?id=8480173), unchecking the Safari Preferences box fixes the issue.