Some further clarification.
The exception you probably see right now (in latest released F#, be it a latest Oct 2009 CTP or VS2010 Beta2) is a manifestation of a bug in Async.StartChild, since fixed.
On our current internal bits you will see an exception which gives you much more clue as to what’s going on:

> System.Exception: multiple waiting reader continuations for mailbox
   at <StartupCode$FSharp-Core>.$Control.-ctor@1856-4.Invoke(AsyncParams`1 _arg10)

And here is the reason for that: as others noted on this thread,

let rec waitForMsg () =
        async {let! msg = inbox.Receive()                          
               let! _ =
                        async{
                           match msg with
                            | CallMsg (replyChannel) ->
                                   replyChannel.Reply("strResult")
                            | _ -> failwith "Invalid Message"
                           return! waitForMsg()
                             } |> Async.StartChild
               return! waitForMsg()
               }

you call waitForMsg() (i.e. inbox.Receive()) twice simultaneously in two different threads. This is not allowed – access to mailbox should be serialized in our implementation.

If you want to parallelize your replies, by all means do so but just keep waiting for messages on a single thread:

let rec waitForMsg () =
        async {let! msg = inbox.Receive()                           
               let! _ =
                        async{
                           match msg with
                            | CallMsg (replyChannel) ->
                                   replyChannel.Reply("strResult")
                            | _ -> failwith "Invalid Message"
                           return()
                        } |> Async.StartChild
               return! waitForMsg()
               }

Incidentally, using Async.StartChild only make sense if you actually want to wait on child completion, because Async.StartChild returns the wait async.
Since you are ignoring the return value, you will be better off just using an Async.Start:

let rec waitForMsg () =
        async { let! msg = inbox.Receive()                          
                async{
                   match msg with
                    | CallMsg (replyChannel) ->
                           replyChannel.Reply("strResult")
                    | _ -> failwith "Invalid Message"
                   return()
                } |> Async.Start
                return! waitForMsg()
              }

This also has the advantage of working in released F# versions J
Feel free to follow-up offline at dmitry(dot)lomov(at)microsoft(dot)com

The spawn child looked fishy to me, and I think it was causing the problem. The ``let!'' should rotate to an available thread.

The code below will always get the exception on the second loop for me. But, removing the spawn child doesn't crash.

module messageReplyTest
open System
open System.Threading
open System.Diagnostics
open Microsoft.FSharp.Control

type PipelineTestMsg = 
     | CallMsg of   string AsyncReplyChannel
     | Empty 

type TestPipelineHandler1 (runPipeline : IDisposable -> string ) =
    let rec runPipe =
        MailboxProcessor.Start(fun inbox ->
            let rec waitForMsg () =
                    async {let! msg = inbox.Receive()                           
                           let! _ = 
                                    async{
                                       match msg with
                                        | CallMsg (replyChannel) ->
                                               replyChannel.Reply("strResult")
                                        | _ -> failwith "Invalid Message"
                                       return! waitForMsg()
                                         } |> Async.StartChild
                           return! waitForMsg() 
                           }
            waitForMsg ())
    member x.ProcessPageWithReply () =
//            Console.WriteLine "Prepare to Call"
            let res = runPipe.PostAndReply
                        (fun replyChannel -> CallMsg(replyChannel))
//            Console.WriteLine "Returned from invocation"
            ()

type TestPipelineHandler2 (runPipeline : IDisposable -> string ) =
    let rec runPipe =
        MailboxProcessor.Start(fun inbox ->
            let rec waitForMsg () =
                    async {let! msg = inbox.Receive()                           
                           let! _ = 
                                    async{
                                       match msg with
                                        | CallMsg (replyChannel) ->
                                               replyChannel.Reply("strResult")
                                        | _ -> failwith "Invalid Message"
                                       return! waitForMsg()
                                         }
                           return! waitForMsg() 
                           }
            waitForMsg ())
    member x.ProcessPageWithReply () =
//            Console.WriteLine "Prepare to Call"
            let res = runPipe.PostAndReply
                        (fun replyChannel -> CallMsg(replyChannel))
//            Console.WriteLine "Returned from invocation"
            ()


while true do
    let foo (x : IDisposable) =
        "result"
    let handler = new TestPipelineHandler2(foo)
    let bar = handler.ProcessPageWithReply ()
    Console.WriteLine "Wait for exception"
    Thread.Sleep 3000
    Console.WriteLine "Return from Sleep"

I don't know if it was from removing the irrevant parts. But, you could reduce runpipe to something like this:

 

    let rec runPipe () =
        MailboxProcessor.Start(fun inbox ->
            let rec waitForMsg () =
                async {
                    let! msg = inbox.Receive()                           
                    match msg with
                    | CallMsg (replyChannel) -> replyChannel.Reply("strResult")
                    return! waitForMsg()
                }
            waitForMsg ())