Reading this post helped me figure out why my session style (not cookie, cookie was fine) login was not working in an ajax function yet it was in a regular POST/redirect style flow.
A redirect is not explicitly needed, it is what happens during the redirect (exec_header_redirect()) which is needed. After looking through the code the reason it appears that a proper redirect is needed is that it eventually calls exec_shut_down() which saves the session.
I could not figure out why my session was not saved correctly with the user info inside and this is the reason.