In this paper, we propose using the network-attached disk (NAD) architecture to design highly scalable and cost-effective multimedia-on-demand (MOD) servers. In order to ensure enhanced performance, we propose two schemes, called distributed interval caching (DIC) and multi-objective scheduling (MOS). The DIC scheme utilizes the on-disk buffers for caching intervals between successive streams, while the MOS scheme improves resource sharing by scheduling requests for service intelligently based on four predefined criteria. We then integrate the two schemes and study the overall performance benefits through extensive simulation. We also study the effectiveness of the proposed DIC scheme by developing an analytical model that estimates the performance limit of DIC. The results demonstrate that the integrated policy works very well in increasing the number of customers that can be serviced concurrently while decreasing their waiting times, and that the performance improvements scale with the number of disks in the server.