How to decide between module_exists and function_exists?
You should always program to the API and not the implementation.  If Drupal provides a mechanism to do something, use it.

module_exists() should almost always be used for soft dependencies on something provided by a Drupal module.  You can always get version info, and decide what to do, using system_get_info().  There have been cases where functions are available when modules have been disabled (some of the class autoloader modules have has this problem).

function_exists() should be reserved for checking whether a PHP feature or library is available.  Core has some examples of this in some of the drupal_ wrappers for string manipulation and character set conversion.