I have provided my suggestion on Exchange 2010 UM side ( I have been working on Exchange 2007/2010 UM with CS1000 , OCS2007/Lync 2010)
1.Create a UM dialing plan (type :unsecure and extension, 5digits)
2.Create a UM IP gateway associated with this dialing plan (the UM IP gateway should be the IP office IP address ,who send the INVITE to UM)
3.Optionally, you can create a Auto-Attendant assoicated with this dialing plan For example ( 5 digit 55000)
Then you can modify the UM dialing plan for system access number to 50000.
Now, you can creat mailbox receipt with UM enabled including the mailbox extension number, PIN.
For Avaya IP Office side, I am not familiar but can provide some clue
1. You must point to UM IP address for messaging
2. The number defined in IP office and UM should match