One approach I've heard of, but not used myself, is for each user to have a package (eg, .deb, .rpm) which contains their ssh public key config, as well as any dotfiles they like to customise (.bashrc, .profile, .vimrc etc). This is signed and stored in a company repository. This package could also be responsible for creating the user account, or it could supplement something else creating the account (cfengine/puppet etc) or a central auth system like LDAP.
These packages are then installed onto hosts via whatever mechanism you prefer (cfengine/puppet etc, cron job). One approach is to have a metapackage which has a dependency on the per-user packages.
If you want to remove a public key, but not the user, then the per-user package is updated. If you want to remove a user, you remove the package.
If you have heterogeneous systems and have to maintain both .rpm and .deb files, then I can see this being a bit annoying, although tools like alien might make that somewhat easier.
Like I say, I've not done this myself. The benefit in this approach to me is that it supplements a central LDAP system and central management of user accounts, in that it allows a user to easily update his package to include his .vimrc file, for example, without having to have that file managed by tools like puppet, which a user may not have access to.