Bulk reduce image size with Paint.net

It sounds like you're getting an OutOfMemory exception. The .Net OutOfMemory exception is a bit misleading. It's much more common to see this exception when you run out of address space, which is a little different than physical memory. This means things like checking the task manager to see how much memory is used may not help you track the problem.

Instead, the problem is likely the result of a bug in Paint.Net, such that certain parts of the image are placed by the .Net runtime on something called the Large Object Heap. The file is then loaded in such a way that this same set of memory is created and destroyed several times, perhaps such that it gets a little larger each time. The garbage collector doesn't free up or compact the address space from the Large Object Heap very well (even though the physical memory was released or paged), and so suddenly you get an OutOfMemory exception.

The solution is either for Microsoft to change the behavior of the .Net runtime with respect to the LOH, such that it can go in and compact the LOH in certain situations (perhaps on request, or before throwing the OutOfMemory exception), or for the Paint.Net program to fix the way it loads the file such that it correctly grows whatever existing data structure is causing the problem, rather than recreating it over and over.

Paint.NET doesn't seem to be able to do this natively. Take a look at the utilities on this page:
http://www.comsquare.ch/index.php?option=com_content&task=view&id=36&Itemid=55

Specifically, pdn2png can save each layer into a separate file with the /split option, like so:

pdn2png /split yourfile.pdn

Alternatively, for something with a graphical interface, try this:
http://forums.getpaint.net/index.php?showtopic=9704

I did a quick test with a 2-layer PDN file, and both seem to work as advertised.