(I believe) DBD::mysql adds single quotes to all its bind variables and (I believe) MySQL 5.x is now much more strict about correctly quoting identifiers (like column names).

That's a lot of needless speculation. It assumes that DBD emulates placeholders (needlessly, because the driver doesn't support them or because the database doesn't support them). Ideally, the change is that 5.x started supporting placeholders. I don't know which one's true, but it doesn't matter.

"select * from clients order by ?" and passing "last_name" won't work anymore

You are segregating the query and the parameters incorrectly. Elements of both getQuery() and getQueryVars() form the query. You need to reorganise your data. Using your notation, the minimal change would be:

$dbh->prepare( build_query( $dbh, getQueryInfo() ) );
$sth->execute( getQueryVars() );
[download]

or

$dbh->prepare( build_query( $dbh, getBaseQuery(), getOrder() ) );
$sth->execute( getQueryVars() );
[download]

It has been suggested that $dbh->quote_identifier() will do the trick, and this is undoubtedly so if everything were hard-coded.

That makes no sense. If the query was hard-coded, you wouldn't need quote_identifier.

The following builds an ORDER BY clause with nothing hard-coded:

if (@order) {
    $query .= ' ORDER BY ' . 
        join ', ',
        map { $dbh->quote_identifier($_->[0]) . " $_->[1]" }
        @order;
}
[download]

@order is expected to resemble the following:

my @order = (
    [ Brand => 'ASC'  ],
    [ Model => 'ASC'  ],
    [ Year  => 'DESC' ],
);
[download]