Is it possible to generate or update a recovery parition We have started to replace hard drives in some MacBook Pros and Airs that are about 3 years old.

We found out the hard way that FileVault encryption requires a recovery parition. 

If we install Mountain Lion or Mavericks from the USB installers that we have created, we do not get the option to create the recovery partition.

So far, we have only found 2 methods:

1) Internet Recovery - This takes a long time and usually installs Lion, which then requires an upgrade to Mavericks.  After upgrading to Mavericks, the recovery partition will reinstall Lion if the recovery partition is used to reinstall Mac OS X.

2) Take it to the Apple Store - This is not always practical in a business environment.

Is there any other way to do this?
In my experience, there is never an "option" to create a Recovery Partition. I've done a number of clean installs from DiskMaker USBs and each of them automagically resulted in recovery partitions being created during the installation process. For me, the typical upgrade process is to either wipe the existing drive or install a new one, use a DiskMaker X-created USB to install the version of OS X desired and then import the required apps, data and user profiles from Time Machine.

This has worked flawlessly with Lion, Mountain Lion and Mavericks on a variety of systems.

Internet Recovery always installs the version of OS X that was originally shipped with the product. Local Recovery will reinstall the OS X version that was used to create the recovery partition. A typical scenario would be to take a virgin disk installed in a system, boot to a Mavericks USB installer, use Disk Utility to create the install partition and then start the installation process. The OS X installer will resize the partition you created automagically and create the recovery partition. A reinstall from Local Recovery would feature Mavericks in this case.

I understand that you're seeing something different, but I have yet to see an install with Lion or newer that was missing its Recovery Partition when the install was done on a wiped or new HDD. A system with a series of in-place upgrades will miss out on the Recovery Partition, e.g., Snow Leopard to Lion to Mountain Lion, but that does not appear to be the scenario you're discussing.