I've published a service and added it to a Web Map in ArcGIS Online. When I Edit the map and scroll down to Properties/Application Settings, only Routing, Measure Tool, and Basemap Selector are available (and checked). From what I've read, I should see an option to enable Search here. I check the Service Editor (in ArcMap) and Query is checked under Capabilities/Mapping.
Am I missing something?