How do you display cross-contact searches?
Try creating a smart group of the indiviuals - you should be able to search for all individuals with that particular relationship. You can then export the contact info. 

When exporting, you'll need to select 'Individual' > Relatonship (e.g. 'Employee of')' > Organisation details for each of the address fields

Actually, thinking about it, that might be the problem with your attempt - try selecting the export field 'Organisation' > Relationship (e.g. 'Employer of') > Individual details.