Same problem with my prior car. My 325 did the same thing. I went the same route you did, then had it towed to the shop...STARTER replaced, never happened again.
Replaced battery, checked keys, fuses, connections...etc.
Almost every thread that starts this way, ends with a new starter. Not all of them mind you, but most. And there have been many.
Good luck, please remember to report back with your resolution