"LP needs to have its routines reloaded during the program's duration"

You could use Class::Unload to unload the LP package before loading it again.

That said, the entire architecture you're describing sounds weird. I'm pretty sure a solution exists using object orientation, inheritance and dependency injection to solve your underlying problem without any of this FP/LP/GP stuff, but you've not described your underlying problem in anywhere near enough detail.

"Another nice feature (although not essential) would be to allow the user NOT to specify the package name, and have the program default to FP::routine if it exists, then LP::routine if it exists, before finally defaulting to GP::routine (and returning an error if the routine doesn't exist in any package). I would also need the user to be able to over-ride this by explicitly specifying the package..."

Write all your functions as class methods. That is; functions which are called like:

Package->function(@args);   # like this
Package::function(@args);   # not this!
[download]

That way you can create an uber package like this:

{
  package AllP;
  use base qw( FP LP GP );
}
[download]

Then calling AllP->function will automatically search FP, LP and GP in that order.