I have experience monitoring this size of network. In addition, I'm always evaluating new possibilities when it comes to monitoring solutions.
That said, I'm coming from more of a Microsoft perspective than you are, and I'm not even sure if I would consider some of the solutions you mentioned enterprise-level solutions, but I might still be able to help.
Almost every monitoring system is going to consist of a few common components - the database and the management servers. (NetIQ, Nimsoft, Quest, VMware, SCOM, just to name a few.)
The amount of hardware you're going to need depends greatly on just how you plan to do your monitoring - specifically - how many data points you want to capture. For the most basic stuff like CPU utilization, memory, storage space, etc., your requirements will be less. If you want to monitor a huge slew of application metrics like how many web requests per second your hosts are getting, scanning logfiles for keywords, etc., well then the amount of data collected by your monitoring system will be much larger, and all strict hardware requirements are going to increase.
Other things to consider are factors such as: do you want to load agents on every machine (typically allows for more detailed info,) or do you want to try to go completely agentless? Are you monitoring all physical machines, all VMs, or a mixture of the two? How about network equipment, are you monitoring that too? In big heterogeneous networks like this, what you typically end up with are multiple solutions running together to cover all your bases. If you have a whole boatload of VMs to monitor, certain solutions like VMware VC Ops and Quest vFoglight get information from vCenter (or multiple vCenters) itself, which means a lot of the metrics are more accurate than if they were measured on the VM itself, and it also means you may not have to load an agent on the VM. You can also typically squeeze more machines onto a VM-only monitoring solution. VMware VC Ops has customers today that are running 10k VMs on a single instance of VC Ops.
That said, in my personal opinion VC Ops is almost like more of just a big fancy analytics engine than an actual monitoring solution. It's kinda' cool to see it tell you "based on your current growth, the ESXi host [x] in Datacenter [y] will reach capacity in 30 days."
Alright, so in general, there are a lot of different ways to design a database, but remember that you need high availability. You cannot work in such a huge network and take ownership of a monitoring solution that will go dark completely if one of your database nodes go down. So don't buy 1 HP Proliant server. But two. Or three. Cluster them. Plan for HA. So price that out -- $30 grand?
Secondly, a lot of these solutions are going to have a "management server" type of role in their infrastructure. In my experience these can typically be virtualized just fine. They act as intermediaries between the agents and the central repository, balancing the load and making sure all the data coming in from the thousands of agents gets inserted into the repository in an orderly fashion. You'll find that in these types of solutions, you have to have a few management servers for HA, but you don't want too many as each additional management server will cause contention and locks as they all just to insert data into the repository.
So plan on one or two virtualization hosts for those. Another $15k maybe? That's just ball park. I don't know if your company is going to be building this on new Cisco UCS gear, or Dell PowerEdges that you buy off Craigslist.
Most enterprise-grade solutions are configurable enough to be able to leverage SQL Server or MySQL or even Postgres. However, very few of them are totally awesome at everything, and what I usually see a company doing is running two or more monitoring solutions in parallel.
edit: Also don't forget to plan for geographical distribution. I have servers that physically reside in Amsterdam that are being monitored from Miami. It's possible, but I'm not altogether proud to admit it.
edit #2: It's also important to note that while some companies are very squeamish about spending money on software - it just depends on the culture of the company - a good company will realize the value of Enterprise support. Just something to keep in mind.