If a given version of Perl can be built and installed with your particular C compiler, it should be able to be embedded as well.

You might consider test-building a Perl version that is still within the Perl p5p support window, which I think (now that 5.20 has been released) is probably Perl 5.18.2 or newer. perlpolicy suggests that the two most recent stable versions (5.20 and 5.18 at time of writing) are supported, and "critical security patches" are handled (to the best of p5p's ability) for Perl versions going back 3 years (this would therefore include 5.16, but probably not 5.14, since its initial release was May 14, 2011).

If you're stuck with Perl 5.8, make it 5.8.9, which at least has all the bug patches that any version of 5.8 will ever get.

Good advice thanks! So far I've been able to get 5.16.3 to compile without jumping through too many hoops on these systems.

probably what we'll end up going with.

5.6.2 with hardened hashes is the best, memory efficient and speed wise. I know of no leaks. I posted my hash patch to p5p some year ago.

The 2nd best is 5.14.4 but it has the mandatory unicode and warnings/Carp overhead. regex cannot exhaust the stack since 5.10 but anything between 5.10.0 and 5.14.4 is not recommended.
I don't have the hash patch for 5.8 which would be needed for 5.8.2 - 5.8.9 (5.8.1 is fine, but then 5.6.2 is better)

I would also strongly recommend against 5.16 or 5.18 for security and maturity reasons, and 5.16 is very half-baked in handling binary names. 5.18.2 still not good enough to be trusted in the wild and hashes are slower.

5.20.0 is a bit better. It tests now at least against rogue syscalls, but still not against binary names, unicode is taking too much time and memory and random hash seeds got more secure but slower.

I wouldn't trust perlpolicy too much as p5p doesn't even understand the simpliest security concepts needed in the commercial environment and does nothing against them. They usually need to year to get it. And they are not too familiar with the code they are supporting. Their release schedule is fixed, so you cannot trust numbers, you can only trust stability, which needs a few major versions.

So:

1. 5.14.4
2. 5.6.2
3. 5.20.0

Oops, I forgot the COW mess with 5.20.

You need to skip 5.20 for a while until COW gets usable and stable. I'm waiting for the next major, but I'm saying the same since 5.16.

Besides actually getting it compiled and getting support for it, think of the strings. The regular expression engine in 5.8 does a lot of recursion in situations where later versions iterate when possible. Unicode support has changed a lot. Regular expressions are now first-class entities (since 5.12.0 I believe).