Possible optimization

It's true that implementations of hook_themekey_global() are called on every page request.

But the optimization you describe, to only run some code if the related property is used in a rule, already exists.
Instead of implementing hook_themekey_global() you can define a callback function in hook_themekey_properties(). That's the way most properties in ThemeKey and ThemeKey Properties are implemented.

ThemeKey 7.x-1.x contains an example module. Please have a look at this example.

Nevertheless, maybe we should improve the documentation.

I checked the contents of the README.txt file and cannot see what you are talking about. Also, if that's the case, shouldn't the node, user, etc. make use of that optimization?

That's what they do! The properties are not set using hook_themekey_global() but through callback functions. Please have a look at the implementations at modules/themekey.ENTITY.inc.

I had a look at your MobileKey module. I'm convinced that the functionality could be achieved in an easier and more efficient way:

function mobilekey_themekey_properties() {
  // Attributes for properties
  $attributes = array();
  $attributes['mobile:device'] = array(
    'description' => t('Mobile: Device - the name of device, "desktop", "mobile", or a specific group such as "blackberry" or "ipad". All desktops are mark "desktop".'),
    'validator' => '',
    'page cache' => THEMEKEY_PAGECACHE_SUPPORTED, // FIXME I'm convinced that page caching won't be supported
  );

  // Mapping functions
  $maps = array();
  $maps[] = array(
    'src' => 'system:user_agent',
    'dst' => 'mobile:device',
    'callback' => 'mobilekey_user_agent2device');

  return array('attributes' => $attributes, 'maps' => $maps);
}

Therefore you have to add a dependency to the module ThemeKey Properties as well.
BTW I see a lot of redundancy to some properties provided by this module. Maybe you should consider to make some use of them to reduce your code. We already detect Operating Sytems and Browsers. So the device is not that far away.