10 to 15 minute gap between shutdown and restart is way more than plenty for the EM to realize that it disconnected. During that time, do you see in the Investigator that the Agent becomes grayed out?
To figure out if you're having a performance issue, there are many ways.
1. Message in the EM log such as "outgoing message queue not moving"
2. Message in the EM log such as "outgoing message queue moving slowly"
3. Message in the EM log such as "clock skewed" or "pausing to allow system clock to catch up"
Double check your Agent log and EM log to ensure there is a "disconnected" message acknowledging that the Agent did indeed disconnect.
One other thought is that a thread may still keep alive after a shutdown and thus causing the EM to think it is still up.
I would recommend opening a Support ticket and upload the EM log and Agent log to the issue. Also if you could reproduce this with DEBUG enabled on the Agent and EM, this would greatly help us.