Is it me, or is working the system really hard to achieve?

Firstly, commerce isn't an obvious choice unless you're deliberately making a face man and relatively few builds have the aptitudes to acquire it at a reasonable cost - Medic, Techpriest and Sanctioned psyker.

If you don't have it, that's -20 - and intelligence is, again, one of the hardest stats to get a good value at.

Plus, tradeable items are hard to get - in a regimental base you need to trade in a scarce item (a long-las) to get any bonus, and a very rare item (a bolter) to get any bonus if you don't have commerce.

This has led to a certain amount of kelly's heroes/operation petticoat style theft and scavenging from my PCs…

Yeah, Intelligence/Knowledge is a fairly restrictive Aptitude combination for Commerce - especially due to the skill's importance in performing requisitions. Perhaps Intelligence/General? That way, the Intelligence-based specialties would still receive the biggest discount and serve as the primary sources of acquisition, but groups would not be forced to include one of the three specialties simply for a feasible chance to requisition an item.

As a side note, one would think Common Lore would also use General, rather than the extremely limited Knowledge aptitude. It's not extremely specialized information, after all, just general experience and whatnot.

Are you using the Time Spent/Front Active/War Conditions variables? I would definitely throw the players a logistical bone with the regiment presence variable as well.

Yes and no - it's a multi-regiment base but the front is faltering (which I expect to be quite common because that's when you get the cool desperate missions, after all!)… the bonuses quickly balance out.