I'm going to post my "solution" for anyone interested, which really isn't a solution but it's what I had to do. Hopefully the Survey123 team sees this and can investigate for future releases:
After being 100% certain that the feature service and survey were share correctly, I decided that something wonky happened in Survey123 that I wasn't going to be able to fix. For some reason, even though my feature service was editable by users in my organization, Survey123 was set to allow submitters to "Only add new records" instead of "Add, update, and delete records". This setting was greyed out in the Survey123 website because it is a non-hosted feature service, and Survey123 would not allow me to change it.
I deleted the survey completely and created a new one from scratch. This time, the setting was correctly set to "Add, update, and delete records". Now all users can edit all survey records.
I made no changes to the feature service after initial publishing, so I don't understand why this happened. My organization is fully invested in Survey123 for our form solutions (even non-GIS), and it makes me very uneasy with all the random issues like this that I encounter. I can't keep having to delete and re-create surveys to get them to work.