We consider streaming of pre-encoded and packetized media over best-effort networks in presence of acknowledgment feedbacks. We first review the rate-distortion optimization framework in such scenarios. Given an estimation of future transmission resources, and knowing about past transmissions and received acknowledgments, a scheduling algorithm is defined as a mechanism that selects the data to send over the network at any given time, so as to minimize the end-to-end distortion for the given communication resources. Since the computational complexity induced by optimal solution is unacceptable for practical scenarios, we propose to limit the solution search space in using a greedy scheduling strategy. However, our work highlights the rate-distortion sub-optimality of popular greedy schedulers, which are strongly penalized by anticipated retransmissions. We therefore proposes an original scheduling algorithm that avoids premature retransmissions, while preserving the low computational complexity of the greedy paradigm. Such a scheduling strategy allows to adapt to network QoS fluctuations, with close to optimal rate-distortion performance. Our experimental results demonstrate that the proposed patient greedy (PG) scheduler provides a reduction of up to 50% in transmission rate relative to conventional greedy approaches, and that it brings up to 2dB of quality improvement in scheduling classical MPEG-based packet video streams.