I've looked online and can't seem to find a proper answer.
We have a client that requires very sensitive data be stored in a database. Is there a hosting company that provides high-level database security (this is for a bank).
Yes, there is. IBM does so. Just happen to know that currently sitting IN A bank and which is moving in this direction. There are some other providers. Basically you dont look for a "stupid web host", you look for a high end outsourcing solution. The usual suspect companies will gladly jump.
Note that "security" does not only mean "yeah, has it", but in most countries ALSo means "can proove it up to standard X". Banking data may / must follow quite some regulations, and you better get a list from your compliance department.
We've had great success using SoftLayer, as long as you don't need a fully managed service. They have a whole private-network infrastructure in addition to their public Internet-facing network.
The private network for example can allow your front-end servers to communicate with your DB servers without ever traversing the public interface. In fact on our hosted DB servers we have completely disabled the public interface, our webservers communicate with them via the private network only.
They also provide a VPN connection that lets you tunnel into the private network and manage your servers without ever opening RDP or any other protocol on the public interfaces. Each user's private network is segregated from everyone else's by a VLAN into which the VPN tunnel connects.
This has worked out quite well for us.