Should accessing addresses via the API always require the 'view all contacts' permission?
According to the API Security page, this is expected behaviour - only the Contact API applies ACLs and such.

Looks like the best solution is to write a custom API that limits available data.