Sometimes the Time & Sales shows trades in between the bid and the ask. How is that possible?

Your two scenarios make sense. You didn't specify the security so I'll toss a third one out which applies to options.

I'm looking to roll a somewhat deep ITM long put down a strike for a credit of $4. The B/A spread on each side is quite wide so I place a vertical spread order for the roll, splitting the B/A on each leg. I don't care what the fill price is for each leg as long as I get my $4 credit. Once in awhile, one or more spread has legs that are filled are well away from the current B/A.

For example, all but one spread are filled at $3 for the buy and $7 for the sell, netting me my $4. The outlier spread is filled at $3.50 for the buy and $7.50 for the sell, again netting me my $4. No advantage or disadvantage to me. However, my fill prices on the outlier are well outside the current B/A spread. This could occur just as well between the B/A spread that you noticed (no Time and Sales quote but it trades there).

My guess is that there's a call buyer or call seller at one of my strikes who either split the B/A poorly or didn't split it at all. The market maker doesn't want that risk so he combines the 3rd party's call with one of my puts in a conversion or a reversal and then fills my other leg $4 away. IOW, he's splitting the B/A for me (capturing half the B/A of my puts) and capturing the bulk or all of the call's B/A spread from the 3rd party.

In Australia we have a system that allows trades to be executed between the bid and ask, I think they call them centerpoint trades. It allows the non retail investors a small advantage in trading over the retail traders. Some may say that is unethical or illegal, but because it requires a willing seller and buyer at that price then one could argue that it really is no different to an off market trade, where two will participants trade exclusively at an agreed price, which is legal and ethical

Thereis a third answer: your bid/ask are not what you think they are.

Particularly in stocks in the USA (but also i.e. canada) there are quite a lot of exchanges all with their own order books. There is one consolidated order book.But there is a possibility that some exchanges have a little different pricing for some time.

i.e. look up https://www.investopedia.com/terms/l/lockedmarket.asp - decribing a similar scenario.

So, it is possible that your bid/ask is from one exchange or the consolidated (fake and a little lagging) book while the trades are per definition from a specific exchange an may have a slightly different bid/ask.