At first, you're true : basicHttpBinding does not support this due to the connectionless /stateless nature of the HTTP protocol.
But I think there is something wrong in your WCF understanding.
Session is a generic concept in WCF. It can be security-based session, in which both ends of communication have agreed upon a specific secure conversation or a realiable session in which messages can be configured to be delivered in order and exactly once, ensuring messages are received even when messages travel across multiple nodes during the conversation.
Both modes allow you to select InstanceContextMode.PerSession. Is this really what do you want ?
WCF security relies on mutual authentication ; If both parties trust the other's credentials (based upon claims), then a secure context can be established in which all messages are exchanged in confidentiality, and all messages are signed to protect their integrity. The security session is unique and you can't reuse it in another conversation.
Here is the problem with your context: the problem is not on Server Side but on Client Side. Because something have to be kept on client and on service, rebuilding the service will flush the whole WCF context on the service (all instances & sessions will be disposed) .There is no general data store associated with WCF sessions (one difference with asp.net session), so a restart will drop everything. However, the client still believe to be authenticated because of its "invalid" context.
To solve this, there is a checkbox for this scenario on the default Wcf Test Client: "Start a new proxy". On WCf Storm, there is a general config in Under the hood/Miscellaneous "always create new proxy".
Note : On production, you will never have this scenario because your service will always be up.
If you follow me you may want to try reliable Session. You can test but I'm not sure this will work.
<wsHttpBinding>
<binding name="wsHttpBindingConfiguration">
<security mode="None" />
<reliableSession enabled="true" />
</binding>
</wsHttpBinding>
Important Note : I don't know your WCF level, but in WCF, Clients and Services must have synchronized configurations (same security, session settings, ...)