Pretty sure is a bug, should work without storing, as that is what MA connectors do.

Strange, I just tried in a plan vanilla Episerver.CMS 12.23.0 with Episerver.Forms 5.7.0, with the following form settings:
Unchecked "Store form submissions", one emailing on submission, no webhooks, no MA.
Form is not disabled. I am able to submit the form, getting the default confirmation message. (no submissions are stored, obviously).

I have the same problem, when I disable "Store form submissions" I get the following error and "Submit" is disabled:
You cannot submit this form because an administrator has turned off data storage.

I have set up "Send email", allowed anonymous submission, disabled all custom forms related code. No errors in console either.

I have tested with Alloy and latest Episerver CMS and Forms nuget packages and do not get the error there.

The source code shows:
SubmittableStatus : {"submittable":false,"message":"You cannot submit this form because an administrator has turned off data storage."},

I have also commented out all security related response headers, to no avail.

Have you found any reason for this behaviour or a solution?

Found it after a while of trial and error.

We were not using Session and adding the following solved the issue:

services.AddSession(options =>
        {
            options.IdleTimeout = TimeSpan.FromSeconds(10);
            options.Cookie.HttpOnly = true;
            options.Cookie.IsEssential = true;
        });

app.UseSession();