This is the solution I used to go with. However, I happened upon one of tye's rants in the CB a number of years ago, where he pointed out that FindBin is broken, and that you're better with File::Spec->rel2abs($0).
I actually have the following in one of my scripts:
use File::Basename qw(dirname);
use Cwd qw(abs_path);
use lib File::Spec->catdir(dirname(dirname(abs_path($0))),'lib');
well. the objections against FindBin I read so far always have to do with using FindBin after you changed the directory. If I had a script somewhere in my repository that does a chdir in a BEGIN block and if such a weird thing is really necessary, I can place FindBin even before that BEGIN block and everything's fine. If the script uses a module that does a chdir in a BEGIN block then I probably have other problems anyway.
So if you know what you're doing IMHO FindBin is handy and safe enough. Do you always use $[ instead of 0 just because a script could set it somewhere? ;-)
Now I think I understood the problem. It is about the PATH searching feature which is only invoked if the script is called via "perl perlscript.pl". (Documented is a workaround to call "perl ./perlscript.pl", though. I guess I never had problems with this because I usually call scripts with the full path or at least bin/script.pl anyway.)
I was informed by Graham Barr that the PATH searching was done only because of a broken SunOS shell many years ago. I asked him because I suspected there must have been a reason for this.
Moritz and I discussed and came to the conclusion that there is no other case where this "feature" would actually be reliable and useful. So to keep the nice short usage of FindBin and to make it work correctly in all cases (except doing chdir() before, since it is actually impossible to obtain the correct path then) I submitted a report to perlbug: http://rt.perl.org/rt3//Public/Bug/Display.html?id=89698
And it appears that neither you nor Graham Barr actually understand what I find funny about searching PATH. It doesn't actually do anything useful (even in the case of a SunOS shell that could use relative paths). (For it to be useful, Perl itself would have to have a strange quirk, one that I'm pretty sure Perl never had.)