Okay, first they gave you a format that you don't support: InDesign -- which may not be as big as Qwark yet, but it IS an industry standard and is in the process of quickly making Qwark irrelevant. Then you go on to say that you support InDesign. I'm confused.
And no exaggerating....the Font Folio a lot closer to $10,000 than $20,000 
You noticed that I listed Paintshop and Office separately from the others. I know that they aren't in the same league, but you didn't indicate that this was an in-house print shop. If you're gonna serve the public you have to support the most common files people bring in to you.
Anyway, I stand by what I said, "Any print shop that doesn't support the entire Creative Suite (which includes InDesign), Macromedia Suite, and Qwark..." They brought you something in InDesign. That absolutely should not be a problem for any pring shop, in house, or otherwise. And converting to PDF is a bad solution when you want quality stuff. Acrobat often messes with colors and quality, and it precludes the printer from making any adjustments needed for the printers, etc.
They should have given you the fonts, of course, but then you should probably have just called them and said, "Hey! You forgot to give me the fonts."
Shmokes, the fact you don't work in the print industry is quite obvious and I don't mean anything bad by that statement. I don't work in engineering or the software industry and won't pretend to either.
Secondly, the only reason I said I supported InDesign is because I downloaded a trial version just for that job. IT will have ---my bottom--- if they find it.

Thirdly, the reason InDesign will not be a PRINT (big difference from DESIGN) standard is because it is not an encapsulated format.
Non-encapsulated formats have the option linking to external resources like other image files and fonts. This really messes us up if a customer brings in a file but forgets to bring the vast array of images and fonts they've used in the process. (happens surprisingly often) And it's even worse if the files come from other states within Australia or even New Zeland. The delay in communication is bad especially if they need it urgently.
This is why PDF and EPS is preferable. We work from word files a lot but always convert them to PDF first so we can see what will end up on paper (On more than one occasion others in the print room have wasted heaps of paper and print time because they didn't proof it first). WYSIWYG in other words.
I have no problem with them bringing in foreign file formats but it is up to them to ask if we support the format and not just dump the CD on my desk and say 'Print it by Monday', which is why I had to go in on Saturday to finish it off (sweet overtime).
The design department is the only department which causes these problems. Even the dumbest customers in company ask those basic questions and make sure we can read the file before they give it to us. This is what was most frustrating and they should know better.
As far as getting the software, have you ever tried getting a company like this to buy software. I had to fight tooth and nail just to get what we have at the moment because bureaucrats have no idea we need photoshop. Just how much it costs and most of the time don't care if we need it. This was the first time we ever got a file in inDesign and therefore probably wouldn't be justified in getting it.
And no exaggerating....the Font Folio a lot closer to $10,000 than $20,000 
Notice I said $25000 -->AU<--. Australia has a bad habit of vicious mark ups on software and hardware, which is why I buy most of my more difficult to obtain stuff from the US. Savings are absolutely amazing even after taxes.

In the end the job got done (ahead of time) but my frustration with the design department is perfectly justified. As I stated, they should know better.