Ok ... vous y étiez presque. Il vous suffit de mettre le champ entre parenthèses pour dire à CakePHP de ne pas traiter le mot-clé BINARY comme nom de champ
Je pense que cela devrait fonctionner :
$this->User->find('list', array(
'fields' => array('User.username'),
'conditions' => array(
"OR" =>array(
"BINARY (`User`.`last_name`) LIKE" => $search_data."%",
"BINARY (`User`.`username`) LIKE" => $search_data."%",
"BINARY (`User`.`first_name`) LIKE" => $search_data."%"))
));