I would make some changes to your structures - namely, I'd abandon most of the arrays and use hashes. %domains would be a HoH where the lower-level H has the same keys as %data. This reduces a dependancy on data order which makes things clearer for me. Ignore this if you want.

%data would become a HoHoA. For convenience and some sort of standardisation, I would have the outter key be lt the inner key. For example, $data{address}{company} would exist, but $data{company}{address} would not, although $data{company}{fax} would exist. Then it's just a matter of putting all your data in all appropriate buckets, and then finding which inner arrayrefs have more than one domain in them.

There shouldn't be much memory usage here - just lots of refs.