Such a cost basis is established (most commonly) by a trade, but also by the transaction type income/mining/gift.
A cost basis is NOT generate by a deposit. A deposit is just the shuffeling of an existing coin and needs a matching withdrawal.
Most purchase pool warnings "There is no suitable purchase to this sale (all purchasing pools consumed). Assuming purchase on the same day for 0 USD" are caused by the fact that there is only a deposit of a coin, but no cost basis inducing transaction before. It is as if this coin gets dropped out of thin air without a cost basis - and when this coin is finally spent, a warning appears.
So the warning in the tax report might be at a much later date than the coin came into the system (without a cost basis) and you have to look through the coin's history to find the origin.
In addition you need to consider that the tax report uses the coins with FIFO. So even if you bought BTC for FIAT on an exchange (=cost basis established) and then sell it for another, the BTC used to calculate the gains might be from a different purchase date and could thus have no cost basis.