This is going to sound crazy, I know, but I have a feeling DBI is actually paying some kind of attention to the internal type of the presented variables.

During diagnosis, I tried to abstract the variable away into an array, which would make a copy and theoretically de-taint the orginal scalar. Then, a few things worked, surprisingly:

my $foo = ''.$key_value;
my $foo = "$key_value";
my $foo = eval($dbh->quote($key_value));   # Desperation
[download]

Also, priming the query with some stupid data did the trick too:

$sth->execute(1,"A","B","C");

Now it just occured to me that the data in $key_value leading up to the call that failed was strictly numeric, except when either a) the code was literally converted to a scalar, or b) enquoted, to force stringification.

Now, the question is, what does this mean?

My busted test case, which I'm curious to see reproduced, is:

my $sth = $dbh->prepare("
               INSERT INTO web_sessions_aux 
                      (wsa_id, wsa_type, wsa_key, wsa_value)
                      VALUES (?,?,?,?)", {});

my $rv = $sth->execute("2012","CRS","crs_search_index",1)
      && $sth->execute("2012","CRS","crs_search_criteria","S")
        ;

$sth->finish();
[download]

Note the numeric in the fourth column (CHAR). Why would this matter?

Update: Solved!
It would seem to be a problem in DBD::mysql which checks the "type" of the scalar being passed to the execute call. From dbdimp.c:

if (!ph->type) {
         ph->type = SvNIOK(ph->value) ? SQL_INTEGER : SQL_VARCHAR;
}
[download]

You can see here that if the placeholder type is not set, it uses the Perl internal representation as a hint. Unfortunately, once assigned, this is never checked again. To clear up the problem, I just assigned straight to SQL_INTEGER and everything is A-OK.