5.6.0 or later. All code I write tends to work with 5.6.0 or later, even if I develop it using the latest 5.8.x. No features have been put into Perl since 5.6.0 that I actually use, so I don't have a pressing need to upgrade. Sure, there are bugfixes, and sometimes, that makes it worthwhile to upgrade. But unless really needed I don't upgrade -- it too often happens working code breaks because of an upgrade (not always because of a bug in a new version - but a change in behaviour can break a set of applications working together).
Code I write tends to not work on 5.005_0x (if only because of 'use warnings'). It's usually possible to change code easily to work with 5.005_0x, but I prefer upgrading the Perl on the intended machine. But that's not always possible or easy.
It has been years since I needed to target 5.004_0x.