Well, I've only actually reached the queen once. I killed her, but died on the way down, with 0 medkits. This was with a scout. Since then, I haven't managed to play it enoguh time straight to create a worthy mortem.
Still, from what I've done, it seems to me that exploration bonuses are given once per story. This is mostly untested, but I don't believe I've ever recieved more than one such bonus per story, and am certain I haven't recieved more than one bonus pery story per tower (e.g. I've never gained a bonus twice on storage tower level 1). This, crossed with the fact that XP per kill is very low and non-worthwhile in comparison (considering the limited amount of ammo throughout the game, much of which is needed to survive the way back down), means that you aren't likely to reach the XP cap anyway, if you're playing effectively.
Now, since I find max. medical skill to outweigh max. sidearms skill throughout the mid-game, I'll take expert medic and advanced sidearms for that while. Here, the difference between a medic and scout is effectively 1,320 points (1800 (medic bonus) - 480 (scout bonus)), which, for illustration, is worth 132 hunter kills and buys more than basic light weapons. The reason I'm happy with being expert medic/advanced sidearms is mainly my frequent use of the combat shotgun, which hardly requires training (though even with trianing, neither medic nor scout benefits cost-wise over the other), and during its use I benefit more from medical skill than I do from sidearms skill. Meanwhile, I'll try keeping a Colt around for the elites, who go down practically like warriors from a standard pistol, backing kraks effectively. For the most part, once I have advanced sidearms, expert medical and a few other skills (I work towards basic light weapons and advanced fitness and perception, out of which scouts have a slight advantage with fitness (240 points at advanced)), I'll start working towards expert sidearms, which I certainly agree is worth having. By this time, the medical skill bonus is fully factored in. I can also choose to advance in light/heavy weapons skill instead of sidearms, gaining an even bigger advantage over a similarly built scout, cost-wise.
In order to gain advanced sidearms skill, often before I engage in any serious combat, I'll scout the bottom story semi-throughly, gaining my first exploration bonus. This is either enough or almost enough (I don't remember) to gain advanced sidearms skill with a medic, and of course gives me some useful knowledge of my surroundings.
One of the reasons I like expert medical skill so much is that even with a healthy elite at point blank range, I'll almost never have to use more than one medkit to reach a point where I can either fire freely for a few turns before healing again, or just hit him with a krak, more than surviving the blast. Otherwise, an elite causes enough damage to rival the amount of healing gained, leading to serious waste. This also means that, when urgent, I can "safely" heard 2-3 elites around me, getting several with one krak and using only 1-2 medkits. Most other targets I kill several at a time with my non-sidearm combat shotgun.
Regarding the marine class, unless I'd want to advance in 2-3 different weapon skills without taking levels in any non-weapon skill, I can't really figure why I'd want to pick it. I agree that HW Specialists are outdone by most classes in most ways, but consider that they're at a bonus on every non-weapon skill, and twice as much with fitness, compared with the marine, and that they're better with heavy weapons, making them significantly superior, unless you abandon both non- and heavy weapon skills almost entirely.