When setting cookies with strict mode, cookies are not set on redirecting. So, in order for the cookies to be set, the page needs to be viewed to the end-user in the browser allowing the cookies to be set.
An approach to this is to redirect using a form post instead of 302 redirect. By rendering an actual page at the end of the authentication process, you're breaking out of the redirect sequence allowing the browser to set the cookie:
<body onload="document.forms[0].submit()">
<form method="post" action="https://that.other.domain">
<input type="_hidden" name="nonce" value="@Server.SomeVariable" />
<input type="_hidden" name="state" value="@Server.SomeOtherVariable" />
<input type="_hidden" name="whatever" value="@Server.Foo" />
</form>
</body>
Hope this helps?