In this paper, we propose and study the behavior of a number of peer-to-peer (P2P)-based distributed computing systems in order to offer efficient and reliable media services over a large-scale heterogeneous network of computing nodes. Our proposed middleware architectures exploit features including availability of high-performance links to networks, usage of exclusive and partial indexing in peers, making nodes "aware" of the content of their own vicinity, replication of objects and caching of popular items, as well as full connectivity among servers if feasible. Through detailed simulation and experimentation, we investigate the behavior of the suggested P2P architectures for video provision and examine the trade-offs involved. We show that under realistic assumptions, the proposed architectures are resilient to multiple peer-failures, provide timeliness guarantees and are scalable with respect to dropped requests when the number of messages in the network increases.