Problema ao usar OR SELECT

Pessoal eu tenho o seguinte código abaixo:

require('../conn.php');
if(isset($_POST['phone']) && isset($_POST['cpf'])):
 $phone = str_replace(array('(', ')', '-', ' '), "", $_POST['phone']);
 $cpf = str_replace(array('(', ')', '-', ' ', '.'), "", $_POST['cpf']);

 if(empty($cpf) && empty($phone)):
 echo "Digite um CPF ou um TELEFONE para Consulta!";
 else:

 $query = mysql_query("SELECT * FROM clientes WHERE (telefone=$phone OR cpf=$cpf)");

 if($query == false):
 echo $query;
 echo "Cliente não cadastrado! Gostaria de cadastra-lo?";

 else:
 $dadosQuery = mysql_fetch_assoc($query);
 echo "NOME: ".$dadosQuery['nome'];
 echo "\n"."ENDEREÇO: ".$dadosQuery['endereco'];
 endif;

 endif;

este código recebe os valores via POST de telefone ou CPF porém nem sempre vem os 2 valores.Quando vou fazer a consulta no SQL utilizo a função OR porém ela nao valida se as 2 condições tiverem algum valor.

Por exemplo:

Se eu tenho somente o valor de TELEFONE e o CPF vazio ele me retorna false e vice versa. Agora se eu tenho valores no CPF e no telefone mesmo que somente 1 deles estiver correto ele me retorna verdadeiro. será que alguém consegue me ajudar?