The simplest solution would be something like the Nessus Suite from Tenable Security...assuming you have someone capable of setting up the scan parameters an running them (ie, someone in your organization who understands both your LOB and security).
At the high-end, you can contract other companies to do this for you.
I can't really offer better suggestions, since I have no idea what Merchant Level you are mandated to meet, your externally facing network footprint, and so on.
Now, I do seem to recall that the guidelines from the PCI consortium require quarterly reporting of vulnerabilities scans of externally facing IP addresses. Why do your PCI Compliance "people" want monthly scans of your internal network?
Anyway, a list of PCI Approved Scanning Vendors is here:
https://www.pcisecuritystandards.org/approved_companies_providers/approved_scann ing_vendors.php (Tenable Network Security is on that list, btw. Not that I'm recommending them one way or another; just want to reassure you that my earlier example was a valid one).