As many people have responded, and as I noted in my original posting, the shebang of perldoc was the first place to look, which I had already changed.
I then tried perldoc -v -f foo to see where it was looking. Lo and behold, perldoc-5.7.0 said it was looking in /usr/local/lib/perl5/5.7.0 (etc). Funny...so I tried a more pragmatic test:
OK, so it seems to be working! But the footer of the paged output says perl5.6.1, regardless of the actual documentation being displayed! Why???
So, reading perldoc's sourcecode, we find on line 328, a backtick system call to pod2man. AHA!! Of course, pod2man-VERSION's shebang points to /usr/local/bin/perl, which is really 5.6.1 . pod2man must get that version number from its perl interpreter (reasonably so), and then sticks it in the footer of the output.
So, I edited perldoc-VERSION to call pod2man-VERSION, and edited pod2man-VERSION to use perl-VERSION in the shebang line.
Mystery solved. Thanks for all of the responses, and I hope that others have found this to be educational.