If you have an Avaya Partner Messaging voicemail system, you can use the record a call feature if you have a 4 or 6 port-licensing card installed.
The rules for recording calls vary from state to state, so check with the local authorities before using the feature.