Recent technology advances in multimedia communication have ushered in a new era of personal communication. Users can ubiquitously access the Internet via various mobile devices. For the mobile devices featured with lower bandwidth network connectivity, transcoding can be used to reduce the object size by lowering the quality of a multimedia object. In view of the monolithic transcoders which only provide transcoding services and have limited performances due to the unknown data types and protocols in the prior research, we propose the architecture of versatile transcoding proxy (VTP). Based on the concept of the agent system, the VTP architecture can accept and execute the transcoding preference script provided by the client or the server to transform the corresponding data or protocol according to the user's specification. In order to enhance the effectiveness of the VTP architecture, we adopt the concept of dynamic cache categories and propose the scheme maximum profit replacement with dynamic cache categories (DCC-MPR). Based on the weighted transcoding graph, scheme DCC-MPR performs cache replacement according to the content in the caching candidate set, which is generated by the concept of dynamic programming. The experimental results show that the proposed architecture VTP and the corresponding scheme DCC-MPR have better performances in many aspects compared to the conventional transcoding proxy systems.