It seems that your deployment process is tailored towards pure perl modules, and just not general enough.

So on to my questions... Given that any module may have an XS module somewhere in it's dependency chain, do I have to keep a separate set of all the libraries for each platform (rather than only the XS ones)?

I think so, yes. But it shouldn't be all that much work, because most pure perl modules are very easy to build once all dependencies are in place.

But I'd chose a different approach: keep a local cpan mirror, and if some module makes trouble during build, write a patch and let your local mirror distribute the patched copy. Then just use CPAN to install everything on your machines.

There's also the problem that at some point a new platform may be added. When that happens, we need to build all the modules for that platform. Our current solution is to have a big make file which supposedly builds the right version of everything. In reality, this never works, and someone has to spend days manually building all the modules. Is there a good way to solve this?

That depends on why the build fails. If it's just management issues (for example dependencies built in the wrong order), you could try to set up a bundle that has all of the to-be-installed modules as dependencies, and let CPAN or CPANPLUS do the work for you. If the build fails because some module just doesn't work on that platform, I see no way around manual building.

Disclaimer: I never maintained a larger cluster of machines, so take these thoughts as ideas only, not as advice.