Keyed-hash of a lot of small numbers Let's say I have a list of several million numbers, with only 6-9 digits of secret information per number (this means that an attacker might efficiently guess the other digits). I have to store the list in an unreadable format and when given a new number I want to efficiently know if I have the number in my list or not.

For this purpose I store the HMAC – SHA 256 of my numbers, using the same secret key to generate all the hashes. When given a new number I use the secret key to compute its HMAC - SHA 256 and perform a lookup in my list.

I am also storing the same numbers encrypted with another key in AES CBC mode, but this field is not useful for searching because of the random IVs.

Is this secure, cryptographically speaking? Will it prevent attacks to "open" the hashes, assuming the secret key remains unknown to an attacker?
As long as the key is secret, your list of MACs is safe and the numbers are not guessable. 

You probably can truncate your MACs to 80 bits in order to save space, as collisions are highly unlikely for $2^{23}$ entries or so.

If your numbers do not repeat and fit into 128 bits, the simple Electronic Codebook (ECB) mode with AES should also do a good job, you just store the ciphertexts encrypted on the same key.