I worked on this some more, and came up with the attached patches 
proposed against the current grep Savannah master (commit 
9ea9254ea58456b84ed2f0c1481ca91cdd325bf7).

For years I've been wanting to write that last patch and I finally got 
around to it.  It improves grep -P's performance by a factor of 1.2 
trillion on one (admittedly artificial) benchmark.  I hope its 1 ZB/s 
scan rate is some kind of record.  The last patch probably won't help 
your test cases, though I hope the other patches do help somewhat.