More Food For Thought:
You are also describing a situation that cars from most car manufacturers can develop. Your Tribute may sometimes wrongly think that you are trying to steal it.
I believe you have the Mazda PATS (Passive Anti-Theft System). Some vehicles with this must send an "enable message" to the PCM (powertrain control module) when proper conditions are met. On some of these vehicles (There are a couple of different PATS) a malfunction and no enable message being sent can result in the car's fuel injectors and fuel pump being disabled (so it can't be stolen). However, on some vehicles the engine will still crank when the key is turned, anyhow.
Some add-on aftermarket remote start kits and some aftermarket audio devices have been known to screw up the PATS and should be disconnected before trying to diagnose the starting problem.
What could be happening is that when your Tribute thinks you are trying to steal it, it goes into a hibernation state for a certain period of time (10 minutes ?). Because of the intermittent nature of the "no start" condition, the vehicle may fire right up after waiting past the theft prevention time period.
Have you noticed anything unusual regarding a security system light illumination, especially when attempting starting ?
Have you timed out ten minutes when it won't start and tried again ?
Have you tried a different key ?
Mazda dealers (and some other mechanics) have access to an 18 page PATS diagnostic service tips Technical Service Bulletin.
"I've never had it in for diagnostics but I've heard that the codes are deleted once it starts. Is this true?"
No. They should remain for a while.
Shortly after an "episode" have a counterperson from an Advance or Autozone come out to your car in the parking lot and see if they can retrieve any Diagnostic Trouble Codes for you. Most do this free of charge. Write them down exactly as given and post them here.