Most times when shops say ‘flush’ with transmissions it acutally means they used an ‘exchange’ machine, where they disconnect the line to the cooler and collect the old fluid as new fluid is pumped in. No real ‘flushing’ going on.
I see nothing that requires you to do anything else besides change it (drain and fill would be fine with me) every 30k from now on. No need to go to the dealer. And your mechanic did nothing wrong besides a little exaggeration.
I was always under the impression that when it comes to transmission fluid, smell is more important than color, and I would expect it to smell burnt if it was as black as described.
I hate to think what this car might have been through. I pulled a travel trailer for several years through thousands of miles over hill and dale with my old 5.7 suburban and the transmission fluid, which was changed once at the mid point of ‘The Trip’ as a precaution, was always pristine in appearance, odor free and never required topping.
I don’t know if it’s too late but I would have asked the garage to save the old fluid for analysis (and a sniff test). I’m with the others here on the merits (?) of flushing.
"Earlier today I downloaded my car’s maintenance schedule. Now I’m really confused. I went through it three times. Unless you are towing with your vehicle Toyota does not appear to have a suggested mileage for changing the trans fluid. Maybe I missed it but I don’t think so. "
You probably didn’t miss it. Manufacturer recommendations for transmission fluid service are terrible. They are designed more toward selling new cars (impression of “low maintenance”) than keeping those cars on the road. Every 30K no matter what is a good interval.