That doesn't sound bad, actually. I like the idea of the more elite space marines having backstories and history, even if it is just a single sentence or paragraph.
That sounds good, but it would require more variables to keep track of marines performance. Like number of enemies killed and such.
For example, after X number of kills and Y kills in a single battle, a marine might be awared a Crux Terminatus.
Surviving suicide missions might give a Imperial Laurel, etc...
Of course, more mission types would be necessary.
Like rearguard (delaying enemies during a retreat), evacuation (protecting X civilians as they evac), sabotage (inflitration behind enemy lines and destruction of their artilery/air power/communications/vehicles), breaktrough (punching a hole trough a enemy formation, assisting the IG), assasination (killing officers/leaders), last stand (no friendly ship in orbit, but have forces on the ground, allies all dead or almost dead)
Generally more mission types where you fight with allies - either you fight with them or you sandwich the enemy, depending on mission type
Each mission might vary in effectiveness depending on the enemy - assasination would hurt orks the most as they would start in-fighting, it would have little effect on some other enemies.
Eldar, since they are illusive in the field, so something that forces them to defend would work better, etc..
Naturally, these types of missions should have a visible effect - on the enemy, the planet, the allies.
Striking at the enemy shipyards may slow down their ship production (takes longer for them to create a fleet, or they create a smaller one), blowing up fuel depots slows down their expansion on the planet, re-capturing it (which is harder) boosts the IG/PDF their power, etc...
All of this would create an interesting power play where you goal would be to weaken the enemy as much as possible, rather than just charge at their main host.