We have a customer that sends calls to off-site, off-company, non-avaya PBXs (so CTI is not an option).

When the IVR send a call to a group of agents (visible to the pbx only as a number, say extension 1234) it should send a kind of "audio whisper" to the agent, communicating the id of the caller. Once the agent has heard this, he can accept the call (by pressing 1) and when that happens, the call between the IVR and the user and the call between the IVR and the agent are merged and the user is talking to the agent, with no IVR in between.

From what we have seen it seems that CCXML should be the solution for this. Is it? Is this even possible?

If not, is there any other way to pass data to heterogeneous PBXs?

SIP or H323?

You can send out UUI data to a call leg. Alot of what you are describing though would need to be implemented on the customer's side in order to interpret the data and perform all the agent interactions and connections as well as how it handles the UUI data, especially in a SIP environment.

For the voice message to the agent we are going to try something like what is described on https://devconnect.avaya.com/public/dyn/d_dyn.jsp?fn=437.

However, I am curious, let's say SIP lines, how could we do this on UUI? Do we need CTI/AES?

You can pass UUI via a SIP call. You need to use shared mode and certain requirements as to how it need to be formatted so CM can intepret it. This is more a CM question though and you mentioned the call is going to a non Avaya system, so again that needs to be considered.

Have a look at this thread:
https://devconnect.avaya.com/public/forum/d_forum_3.jsp?t=11641&f=6