I did some investigation of perl2exe. perl2exe seems to include its own Perl interpreter and libraries. The recent versions of perl2exe should include Digest::MD5 since they are based on 5.8 and Digest::MD5 was moved into core.

If application is running under the Perl interpreter and using Digest::MD5, then Digest::MD5 is installed and working with the normal Perl interpreter. Is the error happening when building the executable with perl2exe? Or when running the executable? The former implies that something is wrong with the perl2exe install. The later implies that something is wrong with the executable. A good possibility is that perl2exe did not detect that Digest::MD5 was needed and did not include it.