Updating to iOS 18.1 didn't fix it alone. I had to also go into the Safari Feature Flags and click "Reset All to Defaults". Now it works every time.
We still can't figure out an solution for our app's customers who will also experience this issue unless they each do the actions referenced above which won't happen.