By going "noun-verb", you are fixing the first 3 dimensions and leaving one remaining (hence the ~1000x reduction in search space for autocomplete). By going "verb-noun" you are only fixing 1-dimension, leaving the other 3 unknown, and autocomplete would have a larger search space.
Putting it another way. If I started a story "the year was 2015", I've only narrow the one time axis, but the "noun/place" hasn't been narrowed at all, so you still have a sphere of possibilities. However, if I started a story "we were on the Golden Gate bridge", I've pinpointed the 3-dimensions of place/noun, and now the reader only has to pinpoint where on the "time-line" we are. And even that timeline has been shortened to a segment of ~100 years.