Well, if the Partner Messaging is at least 4 ports, you can add a Call Recording button to an extension with Feature-24. This will record into the extension's mailbox, and you will hear Joyce-the-Voice announce that the call is being recorded.

If you google "Telephone Recorder", you will find all manner of digital recorders that you can plug into the Aux jack if you need to record on a per-extension basis, or use a t-adapter at the control unit to record on a per-line basis.

If you want to get elaborate, you can get multi-channel recorders that will record everything simultaneously. (big bucks)