Great post Ted! Very helpful. I just wanted to add a few notes from my experience.
1) In a web map in ArcGIS Online, when feature searching a 10.3 map service that does not support pagination the error message returned is "Error: Location '[your search value]' could not be found". I only mention this in hopes that other users Googling this error will be routed here.
2) I've had trouble finding documentation on exactly which databases support pagination. As of press time, this was the most comprehensive list I could conjure up (through testing and research):
Does not support pagination:
Microsoft SQL Server 2008
Oracle 11g
Does support pagination:
Microsoft SQL Server 2012
Microsoft SQL Server 2012 Express
Microsoft SQL Server 2014
Microsoft SQL Server 2014 Express
Oracle 12c
PostgreSQL 9.2
PostgreSQL 9.3
I've personally tested most of these but not all. If I got anything wrong, please feel free to chime in.