This is horrible and seems like you are trapped indeed... it would make much more sense to use the ladies room, even if it would cause problems, they would be at least lesser than what they are as of now, in my opinion... as the other ladies said, please find our what the law says in your state, find a LGBT centre and try to get legal counsel/lawyer support if needed... know your rights and be ready to fight the right way if you must.
Really what I think you should do is find another job... it seems the employer is not sensible at all at your situation, and you should not have to deal with a situation like this... no one should.