I know !!! It's really strange. And yup - everyone is using internet explorer, this is a filler form, and everyone has office 365 (might not have the "remember me" clicked, but they are in the SharePoint site). Some things that have worked - opening a new form with the filled in form open. Once a new form is opened, the user can submit the filled in form. Sometimes saving to their desktop, closing and reopen the form and the form submits. Another one is for a user to open an already submitted form and submitting. Once they do that, the new form works. There doesn't seem to be a consistent fix, mostly a "try this" until something works - aka the bigger hammer approach. The good news - it seems that once a user submits a form, no further problems occur. Either way, I agree that this is very strange. Just wanted to give an update on this in case some of these "fixes" sparks something.
Thanks for your help with this - I do appreciate it.