Finally cracked it, the fasted encoding speed the above methods gave me was 650 Kbyte/sec. I switched to FastPixel for the drawing and added functions to FastPixel to be able to draw pixels via bytes instead of passing Color objects. Also changed to staged caching. New encoding speed: 2-3 Mbyte/sec. That is faster than the speed I get in the winrar bechmark so should be a fast enough starting point for peoples.

The magic, for those interested:
Code: 
let CreateImages file =
    let fileInfo = new FileInfo(file)
    let fileName = DoCorrectFileName fileInfo
    let numOfImgs = CalcNumOfImgsRequired (int fileInfo.Length)  (CalcImgBytes DefaultImgRes.X DefaultImgRes.Y 3)

    [for i in [ 0 .. numOfImgs - 1 ] -> async {
        let header = CreateHeader (i+1) numOfImgs FileVersion fileName
        use fs = fileInfo.OpenRead()
        use bmp = new Bitmap(DefaultImgRes.X, DefaultImgRes.Y, PixelFormat.Format32bppArgb)
        let fpx = new FastPixel(bmp)

        fs.Position <- int64 ((((DefaultImgRes.X * DefaultImgRes.Y) - header.Length) * 3) * i)

        let length = ((DefaultImgRes.X * DefaultImgRes.Y) - header.Length) * 3

        let count = ref 0
        let buffer' = ref (Array.create (length + 1) 0x00uy)
        let GetX y = if (y = 0) then header.Length - 1 else 0
        let realLength = fs.Read(!buffer', 0, (!buffer').Length)
        let buffer = (!buffer').[0 .. realLength - 1]
                     |> Seq.ofArray
                     |> Break 3
                     |> Array.ofSeq

        // Set file stream offset and free temp buffer
        buffer' := Array.empty<byte>
        fpx.Lock()

        // Write header
        for x in [ 0 .. header.Length - 1 ] do fpx.SetPixel(x, 0, header.[x])
        
        // Bytes to pixels
        for y in [ 0 .. DefaultImgRes.Y - 1 ] do
            for x in [ GetX y .. DefaultImgRes.X - 1 ] do
                if (!count < buffer.Length) then
                    match (buffer.[!count].Length) with
                        | 3 -> fpx.SetBytes(x, y, byte AlphaFlags.ALL, buffer.[!count].[0], buffer.[!count].[1], buffer.[!count].[2])
                        | 2 -> fpx.SetBytes(x, y, byte AlphaFlags.RG, buffer.[!count].[0], buffer.[!count].[1], 0x00uy)
                        | 1 -> fpx.SetBytes(x, y, byte AlphaFlags.R, buffer.[!count].[0], 0x00uy, 0x00uy)
                        | _ -> fpx.SetBytes(x, y, byte AlphaFlags.END, 0x00uy, 0x00uy, 0x00uy)

                    count := !count + 1
                else
                    fpx.SetBytes(x, y, byte AlphaFlags.END, 0x00uy, 0x00uy, 0x00uy)

        fpx.Unlock(true)

        return bmp}]
    |> Async.Parallel
    |> Async.RunSynchronously
Anyway, I wanted to ask if some would be willing to run a test program that will bechmark encoding speed? It would require you to download .NET 4 Beta 2 though.