OnStart is always called when the server (rule engine) is restarted, and right, the flags will only be restored when the engine restarts. Flag states are persisted immediately whenever they change so it's not a caching problem.
So either the server isn't being restarted, or it's not really being stopped. If the server device is sleeping, or it's wifi is off/sleeping AM can't send anything (there's a phone management device in AM you can use to force wifi on). I think it depends on your email client whether it's retried - maybe it has a "draft" or "sent" folder? AM won't retry. There's of course no way to send a message when the task is killed so I can't help much there. You could use AM Remote to see if AM is still responding - use an http connection to avoid confusion in case it's AoD that's been killed. Another trick I use for debugging is to use one device state change to trigger a rule to change some other indicator (I usually use a "toggle" action on another bulb or switch) to confirm whether the engine is running.
If AM has been stopped but not restarted when you open AM on your server device this should cause the email to be sent if AM really was killed and not restarted.
Forcing the Device Screen on in AM is pretty effective at keeping servers awake/active, though I do have trouble on some devices with crappy screen sleep functions (my S5 flickers like crazy when it's trying to turn the screen off when it shouldn't).