Is this protocol secure?
Question 2 can be easily answered. Yes, an attacker could easily overload this part of the system.

This may be the first time S sees A's public key. However, S makes sure the signature checks out, and registers A's new state provided that A's previous state is either older or non-existent.

An attacker can easily send their own public key instead of $A$'s key. Then sign with their own private key. The signature will, of course, be valid, so $S$ will accept it. If $S$ ties that key to the identifier for $A$ going forward, then future messages from the real $A$ would be blocked. Also, no $B$ will ever request a message with said key's fingerprint, so it will wait taking space in the message queue, leading to an easy way to fill the queue and stop any new messages from being processable.