Postgres won't use btree index in left-anchored LIKE query
Finally found this after digging through a bunch of tutorials that suggested I was already doing it the right way: http://www-old.bartlettpublishing.com/site/bartpub/blog/3/entry/329 . Relevant documentation is here: https://www.postgresql.org/docs/9.5/static/indexes-opclass.html

Looks like I'm using locale settings (that I didn't touch, just left default) that won't work for btree "like" index usage. I could have sworn that I wasn't seeing this problem before, and maybe I wasn't. I now have to do CREATE INDEX test_string ON test USING btree (string text_pattern_ops);