This is very simple, Perl scripts should always use /usr/bin/perl and should depend on perl5. At the present time you cannot setup a versioned dependency on perl5 as dpkg doesn't support this. However you can be sure that perl5 is >= 5.004.05. If you really need to make sure that you have perl5.005 then you should depend on perl-5.005 (and here you can use a versioned dependency). But you'll have to update your dependency when perl-5.006 comes out and so on, so it's not very convenient.
Take care to include any dependency on a Perl module as they are not automatically detected by the standard tools like the libraries are. Lintian may warn you about such problems.
If the script does have very special needs such as a specific version of Perl then you'll need to use #!/usr/bin/perl-5.004 (I take 5.004 as an example but you should replace 5.004 by whatever old version of Perl you are needing) and you'll need to add a dependency to perl-5.004. If it does furthermore request some binary modules then you'll need to package thoses modules especially for perl-5.004 instead of the latest Perl (being perl-5.005 or whatever else). Those modules packaged for old Perls will have to add the Perl version in their package name. For a module Foo::Bar, instead of calling the package libfoo-bar-perl you'll have to call it libfoo-bar-perl-5.004.
hertzog@debian.org