Eckbert,
I'm afraid I do not have a good answer for you. As you pointed out, this information is available in LocalizedLabelView but it is used by the system only and CRM users will not have access to it. The approach that CRM takes with Reports is to create different reports for each language and specify the labels there. Then when you import the report in CRM, you can specify in the Languages picklist of the Categorization section which language the report applies to. If a user has a given User Interface Language specified in their options, they will only see reports for that language and reports that have All Languages specified in the Languages picklist. I understand that this approach will increase your development and maintenance overhead, but it seems to be the only supported alternative. Hopefully I'm missing something and someone will provide with a better solution, I'm interested in hearing it as well.
Ivan Kurtev