Lock Table cria fila de querys?

Estou com um problema com mysql junto com php que é o seguinte. Minha aplicação recebe callbacks em forma de posts de um outro sistema. Acontece que este sistema manda muitos callbacks de um mesmo pedido.

No sistema eu verifica se o id do pedido já existe, se não existir ele insere e se existir ele atualiza. Acontece que mesmo fazendo uma verificação com uma consulta do tipo COUNT ele está duplicando pedidos no banco de dados.

A estrutura de minha tabela (de forma simplificada) é a seguinte:

Tabela: Pedidos

id - Id do meu pedido em meu sistema, auto increment e chave primária

order_id - id que vem do callback

outros campos...

O que faço quando recebo um callback é:

1 - verifico dando um select count se o order_id vindo do callback já existe na tabela pedidos.

2 - se não existir insere

3 - se existir atualiza

O problema é que parece que ele ignora o count e acaba duplicando os order_id.

Será que isso está acontecendo por conta de receber um callback atrás do outro e não dar tempo de inserir o primeiro e ai no segundo ele acaba nem achando o da primeira inserção?

Se for isso eu pensei em usar LOCK TABLE mas não sei se é a melhor solução e se o comportamento do mysql irá criar uma espécie de fila de querys. Tipo recebe um callback, o script da lock table e verifica se já tem o pedido, se não tiver insere e se tiver atualiza, desbloqueia a tabela, ai sim pega a próxima query que está esperando já que ela encontrou a tabela travada por conta do primeiro callback.