HMAC is a keyed hash which renders simple brute force attacks ineffective unless the attacker is also able to compromise the key.
Even without the key the system is still vulnerable to frequency analysis. For example if it were used to store passwords an simple sort and count would reveal accounts that have common passwords which could then be brute forced using lists of the most common passwords found on the internet. The suggestion of using blind indexes for searching on partial values (i.e. the first letter of a name) would increase the vulnerability.
Even if the attacker doesn't have access to the key if the application is fast enough he may be able to brute force it by passing every possible value and seeing how it encrypts if the search space is small enough (i.e. common passwords).
Secure key storage is always a challenge and the suggestion that the key is stored on the application server instead of the database has some practical problems. The key in many cases will end up being duplicated in code repositories or build scripts which increases your vulnerability to internal attackers. A better system stored half the key on the database server and the other half on the application server which are then XOR'd to get the encryption keys which can reduce the number of potential internal attackers that could recover the plaintext.
Also when recovering from an attack in many cases it may be difficult or impossible to know how many systems were compromised. Without the ability to prove that both the data and the key weren't compromised in an attack an auditor may require that you operate on the assumption that the data was compromised with associated requirements for notification and penalties.
Banks long ago solved the problem of secure key storage with the use of hardware security modules (HSMs) where the key is stored and used on a secure, tamper proof device. This turned the problem of secure key storage into a problem of physical security which the banks were already good at rather than digital security. Where is my key? My key is right here.
These modules are now becoming more commonly used in the ecommerce space (AWS now provides them, for example) but they are still fairly difficult to work with. Some shops will used hardened/audited servers that run encryption/decryption micro-services instead.