Ok... this was "fun" as in Programmer-fun.  A real pain in the keester to figure out, but with a nice huge smile on my face that I did.  (Time to get some IcyHot for my shoulder considering I'm patting it myself so hard! :P  )
Anyway it's a multi-step thing but is surprisingly simple once you figure out everything.  The short version is you need to use both LostFocus and LostKeyboardFocus, not one or the other.
LostFocus is easy.  Whenever you receive that event, set IsEditing to false.  Done and done.
Context Menus and Lost Keyboard Focus
LostKeyboardFocus is a little more tricky since the context menu for your control can fire that on the control itself (i.e. when the context menu for your control opens, the control still has focus but it loses keyboard focus and thus, LostKeyboardFocus fires.)
To handle this behavior, you override ContextMenuOpening (or handle the event) and set a class-level flag indicating the menu is opening. (I use bool _ContextMenuIsOpening.) Then in the LostKeyboardFocus override (or event), you check that flag and if it's set, you simply clear it and do nothing else.  If it's not set however, that means something besides the context menu opening is causing the control to lose keyboard focus, so in that case you do want to set IsEditing to false.
Already-Open Context Menus
Now there's an odd behavior that if the context menu for a control is open, and thus the control has already lost keyboard focus as described above, if you click elsewhere in the application, before the new control gets focus, your control gets keyboard focus first, but only for a split second, then it instantly yields it to the new control.
This actually works to our advantage here as this means we'll also get another LostKeyboardFocus event but this time the _ContextMenuOpening flag will be set to false, and just like described above, our LostKeyboardFocus handler will then set IsEditing to false, which is exactly what we want.  I love serendipity!
Now had the focus simply shifted away to the control you clicked on without first setting the focus back to the control owning the context menu, then we'd have to do something like hooking the ContextMenuClosing event and checking what control will be getting focus next, then we'd only set IsEditing to false if the soon-to-be-focused control wasn't the one that spawned the context menu, so we basically dodged a bullet there.
Caveat: Default Context Menus
Now there's also the caveat that if you are using something like a textbox and haven't explicitly set your own context menu on it, then you don't get the ContextMenuOpening event, which surprised me.  That's easily fixed however, by simply creating a new context menu with the same standard commands as the default context menu (e.g. cut, copy, paste, etc.) and assigning it to the textbox. It looks exactly the same, but now you get the event you need to set the flag.
However, even there you have an issue as if you're creating a third-party-reusable control and the user of that control wants to have their own context menu, you may accidentally set yours to a higher precedence and you'll override theirs!
The way around that was since the textbox is actually an item in the IsEditing template for my control, I simply added a new DP on the outer control called IsEditingContextMenu which I then bind to the textbox via an internal TextBox style, then I added a DataTrigger in that style that checks the value of IsEditingContextMenu on the outer control and if it's null, I set the default menu I just created above, which is stored in a resource.
Here's the internal style for the textbox (The element named 'Root' represents the outer control that the user actually inserts in their XAML)...
<Style x:Key="InlineTextbox" TargetType="TextBox">
    <Setter Property="OverridesDefaultStyle" Value="True"/>
    <Setter Property="FocusVisualStyle"      Value="{x:Null}" />
    <Setter Property="ContextMenu"           Value="{Binding IsEditingContextMenu, ElementName=Root}" />
    <Setter Property="Template">
        <Setter.Value>
            <ControlTemplate TargetType="{x:Type TextBoxBase}">
                <Border Background="White" BorderBrush="LightGray" BorderThickness="1" CornerRadius="1">
                    <ScrollViewer x:Name="PART_ContentHost" />
                </Border>
            </ControlTemplate>
        </Setter.Value>
    </Setter>
    <Style.Triggers>
        <DataTrigger Binding="{Binding IsEditingContextMenu, RelativeSource={RelativeSource AncestorType=local:EditableTextBlock}}" Value="{x:Null}">
            <Setter Property="ContextMenu">
                <Setter.Value>
                    <ContextMenu>
                        <MenuItem Command="ApplicationCommands.Cut" />
                        <MenuItem Command="ApplicationCommands.Copy" />
                        <MenuItem Command="ApplicationCommands.Paste" />
                    </ContextMenu>
                </Setter.Value>
            </Setter>
        </DataTrigger>
    </Style.Triggers>
</Style>
Note that you have to set the initial context menu binding in the style, not directly on the textbox or else the style's DataTrigger gets superseded by the directly-set value rendering the trigger useless and you're right back to square one if the person uses 'null' for the context menu. (If you WANT to suppress the menu, you wouldn't use 'null' anyway.  You'd set it to an empty menu as null means 'Use the default')
So now the user can use the regular ContextMenu property when IsEditing is false... they can use the IsEditingContextMenu when IsEditing is true, and if they didn't specify an IsEditingContextMenu, the internal default that we defined is used for the textbox.  Since the textbox's context menu can never actually be null, its ContextMenuOpening always fires, and therefore the logic to support this behavior works.
Like I said... REAL pain in the can figuring this all out, but damn if I don't have a really cool feeling of accomplishment here.
I hope this helps others here with the same issue.  Feel free to reply here or PM me with questions.
Mark