Have you looked at ‘Dialed Number Manipulation Rules’ in the trunk that you have setup to handle these numbers?
I think ‘+4’ should be entered into the ‘Prefix’ box and ‘004’ into the ‘Prepend’. In the match pattern box you could put ‘XXXXXXXXX’ to match the rest of the number.
When the number is dialed and is forward to the appropriate trunk via the Outbound route, the ‘+4’ will be stripped and ‘004’ added to the start of the number.