OK, I've an idea how this could work, but I don't have the possibility to test it at the moment.
Now consider these three commands (would need Unix-ification if you're not on Windows):
gswin32c ^
-sDEVICE=pdfwrite ^
-o p1.pdf ^
-dFIXEDMEDIA ^
-sDEFAULTPAPERSIZE=a4 ^
-r600x600 ^
-dDEVICEWIDTHPOINTS=842 ^
-dDEVICEHEIGHTPOINTS=595 ^
-c "<</PageOffset [0 0]>> setpagedevice" ^
-f c:/path/to/first.pdf
gswin32c ^
-sDEVICE=pdfwrite ^
-o p2.pdf ^
-dFIXEDMEDIA ^
-sDEFAULTPAPERSIZE=a4 ^
-r600x600 ^
-dDEVICEWIDTHPOINTS=842 ^
-dDEVICEHEIGHTPOINTS=595 ^
-c "<</PageOffset [168.4 0]>> setpagedevice" ^
-f c:/path/to/second.pdf
gswin32c ^
-sDEVICE=pdfwrite ^
-o p3.pdf ^
-dFIXEDMEDIA ^
-sDEFAULTPAPERSIZE=a4 ^
-r600x600 ^
-dDEVICEWIDTHPOINTS=842 ^
-dDEVICEHEIGHTPOINTS=595 ^
-c "<</PageOffset [336.8 0]>> setpagedevice" ^
-f c:/path/to/third.pdf
Barring any mis-calculation on my part, these "print" your first 3 PDFs onto an A4 landscape medium, but shifting the page offset for each one by 'n*(1/5 of the landscape width)' points, starting with n=0. (A4 is 842x595 points). You get the idea...
Now you'll have 3 (and later: 5) new PDF files without any additional bitmap graphics.
Your job remains now to use pdftk
(which you seem familiar with) to overlay these 3 (5) PDF pages over each other.
Please give some feedback if this works for you. (And don't let the Black Hole escape :-) ).