Unfortunately, my solution was to switch my forms over to Contact Form 7 instead.
I did learn one more piece of information. This strange behavior described above seems to be server-specific. I only noticed it on one site after I transferred it to a new server. It seems the _wp_session cookie may not affect all servers equally, which makes this issue harder to debug.