One other approach you could consider (as a last resort, perhaps, if the mysql-centric approaches fail), is to have your perl script use a semaphore file, such that whenever there are multiple instances of the script running simultaneously, the chunk of code that does the database transaction can be made atomic, and when two or more processes try to do that chunk at the same time, the semaphore file will "serialize" them.

I posted a pretty good/simple semaphore file module here (drawn from a Perl Journal article by Sean Burke).

I actually had a recent case using Oracle on a solaris server, with a remote windows-2000 box running up to 12 simultaneous instances of a given perl script, each instance doing a pretty heavy query-for-update; when I left it to oracle to manage the contention, it seemed like the delays in servicing the queries were multiplicative -- time to complete a given query varied according to the number of pending requests, and as a result, some requests were pending for a very long time); when I included the use of a semaphore file in the script, so that the queries were serialized on the windows box, the delays became simply additive -- now the actual query execution always took roughly the same time.