How can I use object oriented principles in the following scenario?

I have 3 car rental agencies. Each agency requires the data in XML, but in a different format, for example:

Agency 1

test
test

Agency 2

test
test

07/20/2012
07/25/2012
100

Agency 3

test
test

As you can see from above, all 3 basically contain the same information, altough this doesn't have to be the case (some can contain more or less information), but it is structured different, so the way I access it is different. What is the best approach to take so I can write the most minimum code, but be able to adapt to new rental agencies that come along with a different structure?

Right now, I am doing something like this:

public class Agency1
{
SubmitRental()
{
//Parse XML for Agency 1
}

//Other methods for agency 1
}

public class Agency2
{
SubmitRental()
{
//Parse XML for Agency 2
}

 //Other methods for agency 2
}

public class Agency3
{
SubmitRental()
{
//Parse XML for Agency 3
}

//Other methods for agency 3
}

In the above, the classes contain the same methods, but the way they are implemented is different. There are some methods, properties, etc that are in some classes, but not in others. Are interfaces the best way to approach this? If so, should everything be made an interface?

In the XML samples above, the data was the same, but the format was different, which led some to bring up mapping the all the different formats to a set of common classes, but what about the scenario where not only is the format different, but the data is different as well?

For example:

Agency 4

John Doe
193048204820
3/4/64

Assuming all three companies require the same information, create a base class "CarRentalInformation." This information will store/transmit all pertinent information.

Create serializer/deserializer classes for all types of can rentals you need. You could probably use the factory pattern effectively here even if you need specialized information for each type you need.

The logic could then be written as

public List GetCarRentalInformation(string XML)
{
   CarRentalXmlType xmlType = this.DetectCarRentalXmlFormat(XML);
   ICarRentalFactory deserializer = this.GetCarRentalFactory(xmlType);

   return deserializer.Deserialize(XML);
}

public string GetCarRentalXML(List rentalInfo, CarRentalXmlType xmlType)
{
   ICarRentalFactory serializer = this.GetCarRentalFactory(xmlType);
   return serializer.Serialize(rentalInfo);
}

private CarRentalXmlType DetectCarRentalXmlFormat(string XML)
{
   //do some magic detectivework, and return appropriate type
   return CarRentalXmlType.Budget;
}

private ICarRentalFactory GetCarRentalFactory(CarRentalXmlType xmlType)
{
   switch(xmlType)
   {
       case CarRentalXmlType.Budget:
          return new BudgetCarRentalFactory();
       case CarRentalXmlType.Dollar:
          return new DollarCarRentalFactory();
       default
          return null;
    }
}

public interface ICarRentalFactory
{
    public List Deserialize(string XML);
    public string Serialize(List rentalInfo);
}

public class BudgetCarRentalFacotry : ICarRentalFactory
{
   //contains code to serialize/deserialize XML into CarRentalInformation objects
}

StackExchange Code Review Q#13726, answer score: 3