How can I add custom field validation for one of the fields "within" an addressfield?
I've just chucked a validation function into a dev site with an addressfield and you're right, it's a bit strange. It might be that the address field is marked as #tree =&gt; TRUE, and that's what's causing the long element key string.

Either way, it looks like you're checking the $form variable in your validate function, when the submitted data will actually be inside $form_state['values']. A couple of other minor alterations and you should be able to get it working:

function validation_function(&amp;$form, &amp;$form_state) {
  // Let's at least TRY to keep lines to 80 chars...
  $key = 'commerce_customer_profile|billing|commerce_customer_address|und|0';

  // Get the length of the 
  $length = strlen($form_state['values']['addressfield'][$key]['locality']);

  if ($length != 0) {
    form_set_error('addressfield', t('No double-byte input.'));
  }
}


That example is based on the Commerce add customer form, so you'll need to inspect the $form_state['values'] array in your own form to find out exactly what the $key variable should be but hopefully that'll give you somewhere to start.

Just a note on your use of !== above...be careful with that, it will force PHP to make sure the types of the variables are equal, as well as the value. 

strlen() returns an integer, and '0' is a string, so strlen('string') !== '0' will always return TRUE, regardless of whether the values are the same.