Knowing where the addon should be found is the first thing to sort out. You can either look at the addon source and see where it attaches to, or investigate by hand. Generally you'll find it in the `bl_idname` of the Operator.
  
For example I have an addon called autoVTX for which the Operator code has these lines at the top:

    class AutoVTX(bpy.types.Operator):
        bl_idname = 'view3d.autovtx'
        bl_label = 'autoVTX'

        # ...

This Operator can be accessed from `bpy.ops.view3d.autovtx()`


The `try/except` route is fine btw, as CoDEmanX rightfully points out in the comment. If you know where an addon or operator _should_ be when installed then this _should_ work.


    def doCoolThing():
       try:
           bpy.ops.view3d.coolAddon.foo()
       except AttributeError:
           print("COOL ADDON NOT INSTALLED!")