That sounds like it'd require a huge overhaul to the phone system. At which point... why do the telcos even need to be involved here? VoIP is common enough now that you could just have a menu system before the call and trigger a VoIP call to the right department automatically.
And heck, let's get rid of phone queues while we're at it - just have the agent trigger a callback rather than making them listen to an awful hold music loop for potentially upwards of 15 minutes.
maybe the phone tree options could be described using some sort of markup language.
That's a clever idea, but I can so easily imagine a world in which a company's malformed markup causes a buffer overrun in my phone.
Do you use a browser on your phone?
For example, speaking to your cell phone company, you could see:
This would be customized to whatever phone tree you're interfacing with.