As audio and video applications have proliferated on the Internet, transcoding proxy caching is attracting an increasing amount of attention, especially in the environment of mobile appliances. Since cache replacement and consistency algorithms are two factors that play a central role in the functionality of transcoding proxy caching, it is of particular practical necessity to involve them into transcoding cache design. In this paper, we propose an original cache maintenance algorithm, which integrates both cache replacement and consistence algorithms. Our algorithm also explicitly reveals the new emerging factors in the transcoding proxy. Specifically, we formulate a generalized cost saving function to evaluate the profit of caching a multimedia object. Our algorithm evicts the objects based on the generalized cost saving to fetch each object into the cache. Consequently, the objects with less generalized cost saving are to be removed from the cache. On the other hand, our algorithm also considers the validation and write rates of the objects, which is of considerable importance for a cache maintenance algorithm. Finally, we evaluate our algorithm on different performance metrics through extensive simulation experiments. The implementation results show that our algorithm outperforms comparison algorithms in terms of the performance metrics considered.