PKI is 5% technology, 95% procedures. The basic parts of X.509 certificates are exceedingly simple: that's just signatures. The first usable algorithms for that have been described in the late 1970s, and details had been mostly ironed out by the early 1990s (that's not to belittle cryptographic research of the last two decades, but in practice, PKCS#1 v1.5 signatures are good enough).
Procedures describe exactly what happens, preferably at "key stroke level": sensitive operations like renewal of an intermediate CA certificate ought to be performed by an operator under scrutiny of at least one auditor who checks that no key is pressed, no button clicked unless explicitly specified in the procedure. The scope is large; it also includes physical protections on the room which contains the CA, position of surveillance video cameras...
So the number one question that you must ask is: does the product comes with a comprehensive manual of procedures, or at least procedure templates to be adjusted to the local environment ? Writing these procedures and enforcing them is what will cost most in a PKI. This requires knowing what happens "under the hood": not a question of "programming how to" but more having clear and definite notions of what a private key is and what it can do. If you don't have this kind of knowledge in-house, and the PKI product does not come with enough information on that subject either, then you'll have to hire a consultant, and that's not cheap (I should know).
Authentication, Identity Management and Authorization are not the same thing. When we talk PKI in general, we often have in mind a number of requirements which relate to three distinct activities:
Identity Management: keeping track of users, their name, employee ID, date of last modification, and so on. This part is always needed but can be "implicit" or can be as simple as an Excel spreadsheet if there are only two dozen users. For 20k users, you will need something more evolved.
Authentication: making sure that someone purporting to be user U is indeed user U.
Authorization: knowing and keeping track of what operations a given user U is allowed to trigger, what data it can read and/or write.
These activities are distinct. Some products conflate some or all of them, and this can imply uncomfortable restrictions. For instance, consider Active Directory: as a LDAP server, it can be used for identity management, but its Kerberos component handles authentication; this makes it rather cumbersome to integrate non-password-based authentication with Active Directory.
The three kind of activities must be bridged, but still kept separate. X.509 certificates are mostly authentication, but issuance of certificates must feed on identity management in order to know what to put in certificates (a certificate binds a public key to an identity). A very important lesson about PKI is that certificates are no good for authorization. One of the first mistakes that most people do about PKI is that they try to embed access rights in certificates, and then it fails and they understand that they should not have done that (exact reason is hard to pin down but relates to the inherent asynchronism of certificate issuance).
So this brings a second question to ask to the vendor: does your product allow for separation of identity management, certificate management and authorization, and what bridges are supported between them ?
As an illustration -- not a product recommendation -- consider Microsoft Forefront Identity Manager, a suite which includes several products: FIM Service/Portal for identity management, FIM CM for certificates (a wrapper around a CA, also handles smart cards), FIM Synchronization for bridging identity management with AD servers and thus FIM CM,...
If your PKI has any serious value (and if not, why bother ?), then you will want to protect your CA private key(s) in a Hardware Security Module. Preferably, make the root CA offline, on the basis that an offline CA cannot be hacked in from the network. Distributing the root CA public key in all client systems is a major cost, and you don't want to do it twice, so you really really don't want to see your root CA compromised or lost or both.
Since you still have a lot of certificates to issue, you will probably need to have an online intermediate CA. You can recover from a loss or compromise of that CA without having to redistribute a new root CA key in all client systems (that's the point of separating the root from the intermediate CA), but that does not mean that you would be happy to see your intermediate CA private key stolen. So a HSM for that key would be great, too.
Therefore, ask your PKI vendor the following: are HSM supported ?
Smart cards are like small HSM, but on the client side. Smart card support requires some initialization; at some point, there will be some smart card specific code running on some desktop systems. There again, the PKI product may include some support for that, or not. Smart card vendors may also help.
If your certificates are for encryption, as opposed to signatures and authentication, then you will want some key escrow. Indeed, when some data is encrypted with a private key and the private key is lost, then the data is lost. Thus the need for a backup, somewhere. This is typically the case for encrypted emails. Such backups for keys are highly sensitive (they are a very tempting target for attackers) so they must not be improvised.
Thus: does the PKI solution includes a key escrow system ?
On the other hand, you certainly don't want to escrow keys used for signatures, because this will jeopardize any legal value that could be attached to these signatures (details vary depending on context and jurisdiction, but as a general rule you don't escrow signature keys). This implies that users who want to do encryption and signatures will need two keys, thus two certificates. Hence another question: does the PKI solution support multi-certificate users ?
All of the above is about PKI for X.509. Alternate solutions may exist, like ID-based cryptography (what "Voltage" is about, as linked to by @Dave), or decentralized systems like OpenPGP Web of Trust. A necessary initial step is to write down your requirements. You have the constraints; that's good. But you must also answer the following question: a PKI, yes, but to do what ?
Available technical know how is limited
. If you're intending on supporting "a couple of tenthousand identities", and the other non-trivial requirements, you might want to get some expertise on board to do it right, not just select the right product.