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:
print("COOL ADDON NOT INSTALLED!")