BTW, previously the validation emails worked fine for me and for other members. We have about 200 members, so they have signed up just fine. So, I guess this is not a problem with host.
No, they do not go to spam directory – the emails simply never arrive. I have tested to sign up using different email addresses – same result.
And regarding extra plugins – I am now extra cautious with them. I guess most of plugins are not tested with latest BP, and installing them causes fatal conflicts. Twice my database simply crashed because of them. My host provided a backup, which was pretty old – so we have completely lost several newest members and latest user-generated content. And now – this strange issue with new user registrations… Oh well.