How to distinguish between "Addon is not installed" and "Addon is not enabled"?
If the addon is not 'installed' (i.e. unknown from Blender side), then it won’t be listed in addon_utils.addons_fake_modules. So the solution is:

mod = None
addon_name = "myaddon"
if addon_name not in addon_utils.addons_fake_modules:
    print("%s: Addon not installed." % addon_name)
else:
    default, state = addon_utils.check(addon_name)
    if not state:
        try:
            mod = addon_utils.enable(addon_name, default_set=False, persistent=False)
        except:
            print("%s: Could not enable Addon on the fly." % addon_name )

if mod:
    print("%s: enabled and running." % addon_name)