Problem.cs

using System;
using System.IO;
using System.Threading;

namespace PackagingDeadlock
{
    static class Program
    {
        // Set this to 100, and it works fine - all threads finish and exit
        // Set it to 10000, however, and it deadlocks, as per: http://support.microsoft.com/kb/951731
        private const int MaxWritesInKb = 10000;

        static void Main(string[] args)
        {
            DoWrite("Hello1.zip");
            DoWrite("Hello2.zip");
            DoWrite("Hello3.zip");
            DoWrite("Hello4.zip");

            Console.ReadLine();
        }

        static void DoWrite(string fileName)
        {
            if (File.Exists(fileName))
            {
                File.Delete(fileName);                
            }

            ThreadPool.QueueUserWorkItem(delegate
            {
                var package = System.IO.Packaging.ZipPackage.Open(fileName);
                var part = package.CreatePart(new Uri("/foo.txt", UriKind.Relative), "text/plain");

                var data = new byte[1024];
                var stream = part.GetStream(FileMode.Create);
                for (var i = 0; i < MaxWritesInKb; i++)
                {
                    stream.Write(data, 0, data.Length);

                    if (i%100 == 0)
                    {
                        Console.Write(".");
                    }
                }
                stream.Flush();
                stream.Close();
                package.Close();

                Console.WriteLine("Done! " + fileName);
            });
        }
    }
}

Solution.cs

using System;
using System.IO;
using System.Threading;

namespace PackagingDeadlock
{
    static class Program
    {
        // This version wraps the stream, so no more deadlocks
        private const int MaxWritesInKb = 100000;

        static void Main(string[] args)
        {
            DoWrite("Hello1.zip");
            DoWrite("Hello2.zip");
            DoWrite("Hello3.zip");
            DoWrite("Hello4.zip");

            Console.ReadLine();
        }

        static void DoWrite(string fileName)
        {
            if (File.Exists(fileName))
            {
                File.Delete(fileName);                
            }

            ThreadPool.QueueUserWorkItem(delegate
            {
                var package = System.IO.Packaging.ZipPackage.Open(fileName);
                var part = package.CreatePart(new Uri("/foo.txt", UriKind.Relative), "text/plain");

                var data = new byte[1024];
                var stream = new PleaseDoNotDeadlockDueToBugInFrameworkStreamWrapper(part.GetStream(FileMode.Create));
                for (var i = 0; i < MaxWritesInKb; i++)
                {
                    stream.Write(data, 0, data.Length);

                    if (i%100 == 0)
                    {
                        Console.Write(".");
                    }
                }
                stream.Flush();
                stream.Close();
                package.Close();

                Console.WriteLine("Done! " + fileName);
            });
        }
    }

    public class PleaseDoNotDeadlockDueToBugInFrameworkStreamWrapper : Stream
    {
        private readonly Stream stream;
        private static readonly object sync = new object();

        public PleaseDoNotDeadlockDueToBugInFrameworkStreamWrapper(Stream stream)
        {
            this.stream = stream;
        }

        public override long Seek(long offset, SeekOrigin origin)
        {
            lock (sync) return stream.Seek(offset, origin);
        }

        public override void SetLength(long value)
        {
            lock (sync) stream.SetLength(value);
        }

        public override int Read(byte[] buffer, int offset, int count)
        {
            lock (sync) return stream.Read(buffer, offset, count);
        }

        public override void Write(byte[] buffer, int offset, int count)
        {
            lock (sync) stream.Write(buffer, offset, count);
        }

        public override bool CanRead
        {
            get { return stream.CanRead; }
        }

        public override bool CanSeek
        {
            get { return stream.CanSeek; }
        }

        public override bool CanWrite
        {
            get { return stream.CanWrite; }
        }

        public override long Length
        {
            get { lock (sync) return stream.Length; }
        }

        public override long Position
        {
            get { return stream.Position; }
            set { lock (sync) stream.Position = value; }
        }

        public override void Flush()
        {
            lock (sync) stream.Flush();
        }
    }
}