Object referenced by PointerProperty in Python can not be deleted properly
Based on the suggestion by @batFinger, I realized that if I delete the object using the keyboard shortcut or using the Python console, it is unlinked from the scene and its reference count decreases by 1. Since the pointer property still has a reference to the object, it is not removed from bpy.data.objects. Therefore, I check in my Panel draw() function (which updates automatically) if the desired object is present in the scene as follows:

if context.scene.objects.get(desired_object.name) == None:
# That means that the object has been deleted from the
# scene graph, therefore remove it explicitly
    bpy.data.objects.remove(desired_obj)


This lets me reproduce the functionality inheret to the Blender when dealing with PointerProperty Objects as mentioned in my question.