STM32 CAN BUS missing some transferred messages

Hi, I am trying to communicate with other CAN devices on CAN BUS with STM32F103.

I have enabled "void HAL_CAN_RxFifo0MsgPendingCallback(CAN_HandleTypeDef *hcan)" to receive message interrupt as highest priority and in main loop I am checking if I got the message to which I need to respond.

If I have a message to which I need to respond and TxMailboxes have free space, I respond from main loop like so:

if (HAL_CAN_GetTxMailboxesFreeLevel(&hcan) > 0)
{
 if (HAL_CAN_AddTxMessage(&hcan, &TxMsg.Header, data, &TxMailbox) != HAL_OK)
 {
 Error_Handler();
 }
}

The problem I am having is that "HAL_CAN_AddTxMessage" return "HAL_OK", but often (something like 50/50 chance) other devices do not get the message. So message gets lost? Why adding TxMessage could fail? And why don't I get any indication that it failed?

How to correctly send CAN BUS message without loosing it?