I've written modules before that would use functionality if other modules were installed ... and it was in the module itself, so the checks were done each run, in case it got installed later. (so I could have the debugging modules on the development servers, and put them into production if necessary). Basic logic was:

BEGIN {
  eval { require 'module' };
  if ( $@ ) {
    # ... whatever extra code for when it's not installed
  } else {
    # ... whatever extra code for when it _is_ installed
  }
}
[download]

Of course, I was running under mod_perl, so the checks weren't run every time the module was used ... you'd have to see if the overhead is worth it for your system.