How to avoid "too many parameters" problem in API design?

Question

I have this API function:

public ResultEnum DoSomeAction(string a, string b, DateTime c, OtherEnum d, 
     string e, string f, out Guid code)

I don't like it. Because parameter order becomes unnecessarily significant. It becomes harder to add new fields. It's harder to see what's being passed around. It's harder to refactor method into smaller parts because it creates another overhead of passing all the parameters in sub functions. Code is harder to read.

I came up with the most obvious idea: have an object encapsulating the data and pass it around instead of passing each parameter one by one. Here is what I came up with:

public class DoSomeActionParameters
{
    public string A;
    public string B;
    public DateTime C;
    public OtherEnum D;
    public string E;
    public string F;        
}

That reduced my API declaration to:

public ResultEnum DoSomeAction(DoSomeActionParameters parameters, out Guid code)

Nice. Looks very innocent but we actually introduced a huge change: we introduced mutability. Because what we previously had been doing was actually to pass an anonymous immutable object: function parameters on stack. Now we created a new class which is very mutable. We created the ability to manipulate the state of the caller. That sucks. Now I want my object immutable, what do I do?

public class DoSomeActionParameters
{
    public string A { get; private set; }
    public string B { get; private set; }
    public DateTime C { get; private set; }
    public OtherEnum D { get; private set; }
    public string E { get; private set; }
    public string F { get; private set; }        

    public DoSomeActionParameters(string a, string b, DateTime c, OtherEnum d, 
     string e, string f)
    {
        this.A = a;
        this.B = b;
        // ... tears erased the text here
    }
}

As you can see I actually re-created my original problem: too many parameters. It's obvious that that's not the way to go. What am I going to do? The last option to achieve such immutability is to use a "readonly" struct like this:

public struct DoSomeActionParameters
{
    public readonly string A;
    public readonly string B;
    public readonly DateTime C;
    public readonly OtherEnum D;
    public readonly string E;
    public readonly string F;        
}

That allows us to avoid constructors with too many parameters and achieve immutability. Actually it fixes all the problems (parameter ordering etc). Yet:

• Everybody (including FXCop & Jon Skeet) agree that exposing public fields are bad.
• Eric Lippert et al say relying on readonly fields for immutability is a lie.

That's when I got confused and decided to write this question: What's the most straightforward way in C# to avoid "too many parameters" problem without introducing mutability? Is it possible to use a readonly struct for that purpose and yet not have a bad API design?

CLARIFICATIONS:

• Please assume there is no violation of single responsibiltiy principle. In my original case the function just writes given parameters to a single DB record.
• I'm not seeking a specific solution to the given function. I'm seeking a generalized approach to such problems. I'm specifically interested in solving "too many parameters" problem without introducing mutability or a terrible design.

UPDATE

The answers provided here have different advantages/disadvantages. Therefore I'd like to convert this to a community wiki. I think each answer with code sample and Pros/Cons would make a good guide for similar problems in the future. I'm now trying to find out how to do it.

Answer 1

Use a combination of builder and domain-specific-language style API--Fluent Interface. The API is a little more verbose but with intellisense it's very quick to type out and easy to understand.

public class Param
{
        public string A { get; private set; }
        public string B { get; private set; }
        public string C { get; private set; }


  public class Builder
  {
        private string a;
        private string b;
        private string c;

        public Builder WithA(string value)
        {
              a = value;
              return this;
        }

        public Builder WithB(string value)
        {
              b = value;
              return this;
        }

        public Builder WithC(string value)
        {
              c = value;
              return this;
        }

        public Param Build()
        {
              return new Param { A = a, B = b, C = c };
        }
  }


  DoSomeAction(new Param.Builder()
        .WithA("a")
        .WithB("b")
        .WithC("c")
        .Build());