I once had a similar problem with my wife's car. I started the car (The starter turned the engine as fast as normal.) I stalled the engine and when I turned the key to start it again there was not even a click from the starter solenoid.
Many years ago I had a similar problem with a brand new battery, start the car and it worked fine. Next start - clunk. Next start - fine.
The battery was replaced with another new one and it all worked OK after that.
JimB