[dba-Tech] Seeking your advice regarding false positives for spam lists

Hello All,

I have a customer with six employees.  They are a government linked
childcare related organisation.  Their primary role in life is to dispense
funds to local pre-school child care businesses here in Ireland.

They have been noticing that they often get told that their emails were in
the spam folder of their recipient.

I did some tests yesterday sending from their email addresses to a few of my
gmail accounts and all of their emails went to google's spam folder.

Could they have gotton themselves onto a so called black list?
Do such things really exist and is it really so easy to get on one of these
lists?
I have to presume that if they exist and if you get on one, there is no easy
way to get off such a list?
If so, what do you suggest?  Register a similar domain name and cease use of
the old domain name?

Thanks for your suggestions and comments.

Mark