EM already propagates across the known universe.
"And their difficultly is a bonus in itself - if you want to hide your communications as much as possible"
It is unlikely that such hiding is going to be more effective than existing spread-spectrum techniques, which can already put your communication arbitrarily close to the noise floor, and already exist.
Of course, if you're going to leave science behind you're then going to hypothesize what aliens may have done to somehow break through the noise floor so that's not an option, and, well, this is what I mean by pick one; either use science, or imagine whatever you like, but don't mix the two. There's no reason to believe that the noise floor is penetrable and lots of mathematical reasons to believe it very much isn't.
I meant it in the sense that EM will be attenuated by gas clouds and solid matter due to the high interaction rate of EM, while neutrino (or presumably dark matter) much less so.
And their difficultly is a bonus in itself - if you want to hide your communications as much as possible.
Cost is not always the only metric to optimize. Even today, people try to use quantum entanglement to create communication channels where snooping is detectable.