Looking for a mBTC (or BTC) transaction to determine the validity of BTC.
I don't understand what you are saying. Where are you looking, and how will finding it determine the validity?
How do the transaction fees work.
When you create a transaction you gather up previous outputs to which you have the private key. You make sure that the total value of the previous outputs is at least equal to the new outputs that you create to assign that value somewhere else. If the total of the previous outputs is greater than the total of the new outputs, then the difference is a transaction fee. The transaction fee in addition to the block subsidy is claimed by the miner when they create a new block.
Once all coins are mined, how will a 3rd party be able to make BTC by hosting or bridging transactions.
In 140 years? They'll "make BTC" from the transaction fees.
What will be the cost of the 3rd party? Bandwidth, electricity, nonavailability?
Same as the current cost: hardware, real estate, bandwidth, electricity, maintenance, etc.