So, I am getting the point that taint, and later versions of Perl are trying to make it difficult to use relative paths for modules!

My reading of it is that they are trying to make it more difficult to use relative paths for modules accidentally. It it still trivially easy to use taint mode with relative paths on purpose. I do this frequently.

Is the solution to locate the modules above the website root with a different subfolder for each environment?

My solution is not to run dev, test and prod on the same machine. If you don't have multiple machines (why ever not?) then use multiple paths like this:

/var/www/devsite/lib
/var/www/testsite/lib
/var/www/prodsite/lib
[download]

This keeps the relative path the same across all three sites. Then all you need to do to use your modules is either:

use lib '../lib'; # explicit, hard-coded relative path.
[download]

or to save counting multiple ../../../ -

use lib "$ENV{DOCUMENT_ROOT}/../lib" =~ m#^(/var/www/[a-z]+site/html/.
+./lib)$#; # path relative to docroot
[download]

and you're done. Simple, effective, secure.