We signed up with what used to be an adnetwork. They said they would work with us on a CPA basis. The CPA for us was a signup to our form for a 30 day free trial of our software. It is a cloud based (SAAS) application on a monthly subscription basis. It is aimed at B2B providers. I was clear on who the target audience was and the kind of people who we were looking to signup. However, after the campaign started we were getting very low quality (junk) signups. These were almost all from two gaming sites, they all were chinese names and they were all yahoo email IDs. There were no valid business names. They have sent me an invoice for these as well.
Why don't you dispute the invoice that they sent you? Tell them that they have not delivered the quality leads that they promised and you do not intend to pay the invoice until they do. If there were any good leads from them, you could pay them for those leads (pro rata) as a sign of good faith but otherwise should hold on payment until they deliver as promised.
Most ad networks will also allow you to block traffic from certain websites. If you plan on continuing with this network, I recommend banning any traffic from those two gaming sites as its already proven to be useless and irrelevant traffic.