QoS on a dedicated VOIP network

For Cisco IP phones, you've definitely got the right configuration:

!
mls qos
!
interface UPLINK
 ! Unconditionally trust all QoS markings
 auto qos voip trust
!
interface ACCESS
 ! Look for the Cisco Phone's CDP frames, and trust VoIP from the phone...
 auto qos voip cisco-phone

Should I put "auto qos voip trust" on network uplinks for both directions on traffic?

Yes, auto qos voip trust is required on both sides of any uplink for end-to-end QoS functionality (which is what you'd want, of course).

Will there be downtime to be aware of?

There is no downtime associated with QoS settings. I have enabled qos (platform-wide, and on individual links) with no observable impact; even on links that were heavily utilized, there was no perceivable downtime for transit traffic.

For more info, you can reference Cisco's Auto QoS Whitepaper

Now, I've been told that routers with inbound QoS policies are capable of leveraging the TCP congestion avoidance mechanism by dropping ACKs in order to rate-shape inbound traffic. I've never seen this done in practice, or at least never seen it work; is this a real thing? If so, is it effective? Wouldn't it result in a run of dropped packets every time that a new connection ramped up to speed, before the congestion algorithm could start slowing things down?

I doubt it, certainly for queues as these are relatively TCP friendly anway. Some routers might have tried this strategy to build tcp-friendly policers but I doubt this would be a decent solution. First of all, an ACK can be accompanied by data so you can't really only drop 'ACK's. Secondly, even if that is true for some streams, why would you drop only on the return path? For the TCP stream it's just as good to simply drop the original data and that way you don't waste bandwidth and processing resources between your edge router and receiver.

More likely is to have H-QoS, with a 30Mbps queue/scheduler on the circuit/user level and then multiple smaller-tier queues feeding into that. A simple setup could be to let both TCP and UDP feed into two different 25Mbps queues, so TCP can still leave 5Mbps for UDP and vice versa. Of course more complex variations exist.

Also, consider that ssthresh is usually adapted fairly quick towards your available bandwidth (here 30Mbps - your voice BW). While TCP does not stop increasing cwnd at ssthresh, it will only increase slowly afterwards and disturbing your voice stream only slightly when congestion is reached. However, at the start of the TCP connection, before ssthresh is adapted to a realistic value this will probably significantly disturb your voice flow (albeit shortly). Finally, while it might work okay with only a few TCP streams, when somebody starts 100s of TCP connections (e.g. P2P app) it gets more difficult. It's unlikely that all ssthresh and cwnd values stabilize (quickly) to guarantee fairness, even more if those connections are quite volatile (as is often the case with P2P).

Also, next to drops notice that a saturated connection also has a negative impact on your jitter, this might sometimes be just as problematic (or even worse) than a few packet drops.

In addition to that, however, what if the traffic utilizing the circuit is largely UDP? If a request for a large amount of UDP data is sent to a server, it's naturally going to send the data as quickly as feasible, flood the queue and cause dropped voice packets - but maybe I'm overreacting to that scenario. Is UDP used for any high-throughput internet technologies these days?

You're 100% correct, UDP has no fairness built-in. Many real-time multimedia applications (voip, video conferencing, ...) still use UDP. Tunnels (e.g. for VPN) also usually use UDP to avoid TCP-in-TCP retransmit timer conflicts. So yes, you certainly can have quite some high-throughput UDP traffic on a connection.

More specifically, have you ever personally seen a QoS method that let VoIP work without constant quality problems on a frequently-saturated internet connection without ISP-provided QoS? Have you ever heard of a DSL or cable provider implementing edge router QoS for an application like this? I've only ever heard of that offered as part of MPLS products, is that pretty much a necessity if someone wants downstream QoS?

Well, here the question is of course if many modern internet connections are frequently saturated. In my experience the available BW for a fixed connection often exceeds the average usage. There are always exceptions but usually the bulk of the people have loads of BW, it might still get saturated somewhere, but not that often on your direct access circuit. However, you might encounter it more often in mobile access as this is a relatively low-bandwidth low-reliability shared medium. Currently 4G helps a lot but that will only last this long as mobile BW usage is still growing heavily.

Yes, I have heard providers implementing QoS for multimedia applications. For which applications that might differ a lot from provider to provider. Assume they just qualify traffic as BE unless there is a good reason to do otherwise. But some might indifferently prioritize SIP/RTP.

MPLS is certainly not a necessity for QoS, any decent BNG today also includes quite significant QoS options.