Depending on your release, you may have Caller ID Delay, where the calls will not be sent to the VM ports until either the 2nd ring, or the CID has been detected.
If you don't have that, you would use a calling group, and a time-based overflow to the voice mail ports.
Finally, are you sure that you are set up for CID? Trunks ports and software release that support CID?