It is unlikely for CUCM to send 404 Not Found when device is actually busy. It should return 486 Busy unless there is any parameter in CUCM which I'm not aware.
404 Not Found is sent for unallocated number. Are you sure when call is made from Avaya to Cisco, called party number is correct and Inbound CSS on SIP Trunk (in CUCM) and can see the correct DN?
I agree with Vivek that CUCM will send 'User Busy' instead of 'Not Found'. 'Not Found' is sent for unallocated number.
Please check what Vivek suggest. Also, make sure that the service parameter ' Stop Routing on User Busy Flag' is set to True.
I see that problem is because of SCCP phones.
A few phones are configured as SCCP. These phones are sending wrong status to Avaya. But the SIP phones are working properly.
so this is a compatibility problem of SCCP phones and Avaya