Considering what you'd like to return, I'd recommend the "simple" approach
of writing a custom .NET class marked up with the necessary Xml Serialization
attributes and returning that from your web method. Here's what your Contact
class might look like:

<codeSnippet language="C#">
[XmlType("Contact", Namespace="uri:marsh-samples-contactSearch")]
[XmlRoot("contact")]
public sealed class Contact
{
 #region Fields

 private int id;
 private string firstName;
 private string surname;

 #endregion

 #region Type specific properties

 [XmlAttribute("id")]
 public int Id
 {
   get
   {
     return this.id;
   }

   set
   {
     this.id = value;
   }                 
 }

 [XmlElement("firstname")]
 public string FirstName
 {
   get
   {
     return this.firstName;
   }

   set
   {
     this.firstName = value;
   }
 }

 [XmlElement("surname")]
 public string Surname
 {
   get
   {
     return this.surname;
   }

   set
   {
     this.surname = value;
   }
 }

 #endregion
}
</codeSnippet>

And then your web method would change to look something like this:

<codeSnippet language="C#">
[WebMethod]
[SoapDocumentMethod(ParameterStyle=SoapParameterStyle.Bare, Use=SoapBindingUse.Literal)]
[return:XmlArray("results", Namespace="xmlns="uri:marsh-samples-contactSearch")]
[return:XmlArrayItem("contact", typeof(Contact), Namespace="xmlns="uri:marsh-samples-contactSearch")]
public Contact[] SearchContacts([XmlElement("surname", Namespace="xmlns="uri:marsh-samples-contactSearch")]
string surname)
{
 // NOTE: in the real world you'd probably be looping through a DataReader
 // or something to build these results
 Contact sampleResult1 = new Contact();
 sampleResult1.Id = 131;
 sampleResult1.FirstName = "Drew";
 sampleResult1.Surname = "Marsh";

 Contact sampleResult2 = new Contact();
 sampleResult2.Id = 123;
 sampleResult2.FirstName = "Test";
 sampleResult2.Surname = "Marsh";
       
 return new Contact[] { sampleResult1, sampleResult2 };
}
</codeSnippet>

If you use this exact code, you'll end up with a SOAP request body that looks
like this:

<surname xmlns="uri:marsh-samples-contactSearch">Marsh</surname>

And a SOAP response body that looks exactly how you described:

<results xmlns="uri:marsh-samples-contactSearch">
 <contact id="131">
   <firstname>Drew</firstname>
   <surname>Marsh</surname>
 </contact>
 <contact id="123">
   <firstname>Test</firstname>
   <surname>Marsh</surname>
 </contact>
</results>

HTH,
Dre