Just hopping on to share my similar experiences.
I am PC and my friend is PS5. We can usually get partied up but it takes some time. I send him an invite and nothing happens when he accepts, and vice versa. Alternatively, it may show on his screen that he joined the party, but he doesn't show on my screen and when I ready up, he doesn't get the "searching" pop up.