So for clarification, a CUBE connects IP to IP. Your current configuration is using the 4331 as a Voice Gateway, connecting TDM (E1) to IP (CUCM SIP). You can't use any type of Gateway/CUBE based recording in this configuration that i'm aware of. You also don't need CUBE licenses in this configuration. There are a few different options for recording in your situation that I can think of off-hand:
Span recording - You configure the gateway to span any traffic that comes across it to a recording server. The recording server would need to be correctly configured to accept this traffic.
Built-In-Bridge Recording - You set up recording that uses the Built-In-Bridge on the phone to fork audio from the phone to the recording server via a SIP trunk.
Use a second gateway - You implement a second gateway as a CUBE to record and route all calls through this gateway from CUCM in both directions. That way you would be SIP-SIP. It's not an elegant solution and does add additional points of failure, along with routing changes in the CUCM. Then you could use Network Based Recording, Dial-Peer Based Recording, or SIPRec. For that you would need CUBE licenses. I believe each standard trunk license supports 1 bi-directional call and 1 media fork, but you'd want to confirm all this with a Cisco Partner.
Convert your PSTN from an E1 to SIP - This would of course allow you to be SIP-SIP and use Gateway/CUBE based recording methods.
