There were 2 issues, where 1 raised the other:
1 - When first computing the transaction cost - computeCost did not take into consideration the metadata.fee, which may be greater than config.minfee.
That can cause selecting utxos as inputs, which do not cover the actual cost.
2 - After building and adding the OP_RETURN according to the cc args, there's another computation of the transfer cost - and this calculation takes into account metadata.fee. So now the algorithm picks another utxo to cover that transaction "new" cost.
When picking that utxo, it does not check whether it is already an input in the transaction.
There were 2 issues, where 1 raised the other: 1 - When first computing the transaction cost -
computeCostdid not take into consideration themetadata.fee, which may be greater thanconfig.minfee. That can cause selecting utxos as inputs, which do not cover the actual cost. 2 - After building and adding the OP_RETURN according to the cc args, there's another computation of the transfer cost - and this calculation takes into accountmetadata.fee. So now the algorithm picks another utxo to cover that transaction "new" cost. When picking that utxo, it does not check whether it is already an input in the transaction.