If you stop Starling and still get the "The Stage3D API may not be used during background execution" message, then it's either because the deactivate event is called asynchronously and a few frames get rendered while in background mode before you can stop Starling, or there is something else other than Starling using Stage3D.
I recall reading about background apps being forced to run at 4 fps while in background mode. Does yours fallback to this frame rate or does it keep the frame rate defined by you? What if you stop Starling and also set the frame rate to 0 manually when you get the deactivate event?
Does the iOS 6 notification bar that can also be dragged from the top cause this problem in your app? Have you tried SDK 3.8? 🙂 I know 3.9 is the way to go, but maybe the problem was already present in 3.8 + iOS 6.
Sorry for all the questions but we need to sort this out as it's too critical to be left aside 🙂
Maybe reporting it as a bug to Adobe would help.