This is so completely NOT complicated. Apple, this one's free. Public domain. Hell, patent it and take credit for all I care.
Just have a simple unobtrusive but distinct haptic pattern when the phone goes out of range. Optionally, a unique sound effect. If you happen to lift your wrist at that time, a simple "Phone out of range" screen shows for a few seconds, then goes away. The red icon stays.
To prevent spurious alerts, wait for a certain time period before alerting that the device is out of range. Say one minute. Or even better, make it configurable. (Yes Apple, people actually do like to configure things to their own preferences sometimes.)
You can argue about whether you should be alerted to airplane mode and what to do about people who know they're leaving their phone behind (e.g. in an apartment building, to get the laundry). But here's my argument. As long as the wrist notification is unobtrusive but also distinct, you will naturally learn to ignore it when you "know what's going on", but still notice it when you don't expect it.
Take a home security system for example. Each time you open your door, your system may announce "Front door open." But it was you who opened the door. Over time you just naturally tune out this "notification". But if you were sitting in your living room and you heard "Front door open" and you weren't expecting someone, you'd immediately notice it and jump to attention. This is exactly how it would work with a watch notification. If you know you're leaving your phone - going to the laundry room, going out to the garage, whatever - you'll just naturally ignore the (remember, unobtrusive) notification. But if you hop in the car or on your bike and get a block away from your house and the notification pings, you'll quickly check and notice you forgot your phone before it's too late to go back! Not hard, is it?
Even if you're in public and someone steals your phone, you're not expecting to separate from your phone at that point, so a notification for it being out of range, or Airplane mode being turned on, or whatever, will definitely get your attention. Not to mention, if criminals knew that plenty of people have devices attached to their wrists that will quickly notify them if their phone goes missing, maybe fewer criminals will even bother to try to take an iPhone...?
(Bonus points if Apple implements a "Lock my phone" button right on that notification for LTE watch users or watch users in range of a known Wi-fi...)
I imagine the reason Lookout couldn't really make this a good experience is because of the limits Apple puts on apps. Lookout couldn't do a custom vibration. I don't even think apps can do a custom sound. The notifications stay in the notification center and have to be dismissed. But none of this is Lookout's fault; they're working within the constraints Apple sets. That means the only company that can do this with a good UX is Apple.
Why is it so hard to implement this? Honestly, I paid $549 for a fancy watch that can't even alert me that I'm about to leave my phone behind. I don't drive, so leaving my phone behind easily entails a pricey cab or Uber trip (round trip!).