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.
>>> 'coolAddon' in dir(bpy.ops.view3d)
True
edit
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!")