A media playback device may be operable to determine whether replacement media content corresponding to at least a portion of a received broadcast media stream is available during reception of the broadcast media stream from one or more broadcast sources. At least some of the replacement media content may then be retrieved when personal video recording (PVR) operations are requested during play of the received broadcast media stream, to enable seamless performance of the requested PVR operations using at least a portion of the retrieved replacement media content. Exemplary PVR operations may comprise pausing, fast forwarding, and/or rewinding. The replacement media content may be retrieved from a plurality of local and/or remote replacement servers. Availability of replacement media content, from remote replacement servers, may be determined based on programming data in said broadcast media stream, routing information provided by a broadcast source, and/or by inquiry via one or more cataloguing servers.