Hi Evan,
Available Forward would be my first suggestion. Regarding the message, can you not log in as the user to record the message?
If these are internal calls, another way to do this would be to use the Dial Plan. There is actually a Lab exercise in the ICCE / ICCS classes. You can look for the extension being dialed and then re-map the number to send it out. This also may be the way to go if you use Call Coverage (I haven't tested, but here's my thinking). Set up the Dial Plan to redirect some "internal" number to the desired external one. Then take the object with the "real" internal number and use call coverage to redirect to your Dummy one, which will in turn get re-mapped to the external number. (I'm not sure, but you may have to create a "dummy" object with this extension so that it is seen as "valid" when you are setting up Call Coverage.
If none of these work, then I reckon it'll be a custom handler....
HTH