The temporary solution posted by Gord above works great. At first I thought it would be better to return the label for the address as the option in the list, but I feel it's more valuable to a user to see the first line of the saved address.

There of course is a much more important negative to this and it's that I now have a hacked Ubercart. Would I need to use hook_form_alter to inject the option to avoid hacking Ubercart or is this something that could be changed in uc_store.module? I think this saved addresses functionality is awesome and since a lot of clients are used to the way osCommerce works they expect this kind of behaviour (even though I do try to push anonymous checkout to them).

Someone please chime in and stop me talking to myself!