You've got network intrusion detection and stateful firewalls. Your kernels are patched as far as they can go for exploit prevention. You're using OpenSSH. That's awesome. Now why is it someone can still penetrate your precious servers so easily?
When you begin to secure something (anything, really - buildings, documents, servers) you have to consider everything. Each factor which could possibly be targeted in an attack could be used with any other factor to increase the likelihood of a successful compromise. So each factor has to be looked at in conjunction with every other factor. Yes, this is usually incredibly tedious and mind-bogglingly complex. To help mitigate this you can design preventative measures around each possible attack vector. In other words, add security to everything.
In the example above there's loads of attack vectors just waiting to be leveraged. One example is OpenSSH. A lot of people just use it in it's default form and never add any security to it. This will lead to an exploit. If you allow password entry to an OpenSSH server, just assume it's been compromised. It's so easy to observe a password being typed or intercept it somewhere else it's laughable. Not to mention people hiding passwords under their keyboards or on their monitors! No, a password-protected SSH key is the minimum you should use to allow access to a server. The "something you know, something you have" two factor authentication is far more secure than a single factor. I should stress that this is only true when properly implemented, as bad two-factor can be even less secure than strong one-factor. For more on authentication factors read this and take note of the ways different factors can be exploited (don't rely on just biometrics!).
In newer versions of OpenSSH there are even more methods to harden the authentication process, such as certificate authorities and key revocation lists. Also disabling root logins, having a set list of users allowed to authenticate, disabling old deprecated protocols, ciphers and algorithms, and explicitly dropping any connection with conflicting host keys is a good idea. You should even consider the libraries used by the application - were they built with buffer overflow protection? Is PAM enabled? One need only look around to see the underlying systems of your very critical remote administration software could be rife with potential exploits. For every one exploit known there is probably ten unknown waiting to be found.
Now think about what you have access to on your own system. Consider for a moment what would happen if an attacker used the same methods you do to gain access. Would it be difficult or easy for them? If it's easy for you to access the system, it may be for them. Try to make it more difficult even for yourself to gain access and a potential attacker will have a hell of a time trying to leverage something you've left unguarded. Make your firewalls incredibly verbose and restrictive; you'd be amazed how little can be done to a system when an attacker doesn't know exactly how to use it. Require multiple levels of logins before root can be obtained, and try to minimize any need to get to the root account.
Make all of your services run as unprivileged users. Make scripts to be executed by sudo which don't take any options (and clean their environments) that take care of tasks you may need root to perform. Any admin should be able to perform basic administrative tasks as a non-root user. Make all services controllable by an "admin" group, with each service having its own unique user to minimize attacks from one service to the next. Most services can be configured to start up and bind to a privileged port and drop to an unprivileged user, but for those that cannot there are methods (SELinux, etc) to work around restrictions in an application or system.
Make your configuration also be applied by a non-root user. A good way to think of configuration management is "let the service manage itself." Create your base model or template of configuration management scripts and then create service-specific configuration that can be run by the user of that service. In this way you don't need to worry about an attacker pilfering your configuration management and applying rules to all the machines as root. You can also create more fine-grained controls in terms of what admin (or group) can configure what service. You don't need to worry about a "trusted" user compromising your whole network if you only explicitly grant them access to the things they need to manage.
In fact, consider time-based access control for your entire network. You should expire SSH keys and user access for different services around the same time you expire old passwords. This will force you to improve the method users have to request access and hopefully increase productivity and responsiveness in this area of support. Just don't fall into the trap of allowing anything anyone asks for. Make it easy to get their manager to sign off on a request so at least there's some accountability; you can only benefit in terms of security if somebody thinks they might get fired for granting access willy-nilly.
