Replication is a primary means to achieve fault tolerance in distributed systems. While replication techniques are well known and have been widely applied in distributed object and database systems, they have not yet been extensively used in service oriented systems. However, if the success of service oriented computing shall continue in critical settings, replication middleware will play a crucial role in service oriented infrastructures. Thus, we contribute with a discussion of our experiences in building distributed object and service replication middleware and present the main lessons learned. Our conclusions are drawn from several replication middleware implementations built upon J2EE, .NET, CORBA, and Axis2.