Right before clicking the very last checkmark to start a battle, it is possible to de-select a messenger bird. And then you lose it for the battle.

I did this by accident because I thought the battle had started and wanted to send an order.