Mechanisms of death
The time to lethality (if ever) of a given shot on the target is primarily a function of shot placement. There are two things people die from over the very short term: destruction of the brain, and loss of oxygen to the brain. The typical way the brain goes hypoxic is through loss of blood (and this can happen in less than 3 minutes or so -- even if the bleeding is internal), but another way is for the heart to actually stop completely (the blood is there, its just stagnant).
Snip the base of the brain with a .22, he's out. .50cal to the hips, while spectacular looking, may not kill the brain for a while (if arteries are yanked apart instead of severed bleeding out may take a while). Knock the bottom half of the body off with a truck and the upper half of the body may live for a surprising amount of time (minutes, maybe tens of minutes, but not hours, so your medical tech and response times are critical). Hammer to the base of the skull usually means he's done. Massive blast damage to the body, but not the head, may ultimately turn out no worse for the head than being tackled in a sport (especially if he's got a helmet on -- not for the blast, but when his head hits something as he lands/falls). Linear breaching charges on steel doors sometimes fling a white-hot strip of metal into the room on the other side cutting people apart (which is why we stopped placing them down the middle the doors) -- and sometimes the head-attached part is just fine for a while. etc. The body's reaction to trauma is pretty bizarre sometimes.
Your job in these various cases is to determine the rules for the medical tech and deal with those consequences appropriately. Can people regenerate limbs? (Large caliber or multiple small, high velocity hits can break bodies apart, particularly at joints.) You may wish to avoid these cases entirely, but keep in mind that real gunfights often involve more than just guns.
When the switch is off, it stays off
Brain injuries are not just unrecoverable because magical healing technology couldn't perhaps mend the physical wound, but because the encephalic activity of the brain has ceased. Nobody knows how to flip the switch back on even if you do mend everything involved. Maybe someday, and maybe in your story world, but if this is the case you'll need to explain how that's happening for it to be believable.
Catastrophic heart injuries cause hypoxia almost immediately. But while it appears that someone shot through the heart dies immediately, that's just them passing out as they hit the floor -- the brain will generally remain alive for about 6 minutes, but you've only got 1~3 minutes before serious brain damage begins to set in.
(I've heard that supercooling the brain can prolong this window, but I've never seen it and its hard to imagine that working outside of a lab. I'm mentioning it because you may want to use that as part of your story, but it is definitely not a part of the present-day soldier's experience.)
This brings up the issue of making it to cover. These days we teach that "bullets are the best medicine". Part of the reason is that we don't want people to rush to a place where someone just got shot because that spot is clearly dangerous right then. Another is because most of the time the downed guy can move himself to cover as long as you distract the enemy with suppressive fire. If you're talking to him about how okay everything is and shush-shushing like the movies you are not shooting -- in that case two people are out of the fight. Once covered and concealed he can do whatever he finds immediately necessary on his own: apply a tourniquet, check his body, remove a burning battery from his kit, pop his pills (nearly everyone carries some Motrin and a broad-spectrum antibiotic as a prophylaxis -- combat is hot, filthy and diseased), shoot back, etc.
On Kickin' Chickens and Scampering Skinnies
The stories you hear about people running off, deer leaping fences, chickens dancing around, turkeys trying to fly, etc. after being shot are absolutely true.
Sometimes you nail someone -- know you nailed them because they were right in front of you and you're pretty darn good at this -- and they just run off looking startled instead of hurt, like nothing happened. The first time you see that its surreal and almost comical because for a split second you wonder if your weapon works. You'll find them later, but who knows how long it took before they finally bled out or succumbed to shock? This is a critical period for your super-duper healing tech. In your world, perhaps people just get super afraid (realizing the close call) or super upset (realizing the close call) when this happens instead of succumbing to shock or bleeding out.
This running off after being shot is probably the majority case when catastrophic injury is not delivered immediately. Its not quite like the movies where people just fall over, unless they've been knocked out because of a change in blood pressure. They may bleed out before they wake up, for for a few moments there they are alive, just not moving. This is another critical period for your medical technology -- if its something that doesn't have to be delivered to a patient, but is just a part of them, then maybe they always do wake up in these cases.
A lot of this has to do with proximity. In a gunfight you're going to let any nearby bad guys have a full-serving right away and keep hitting them until they are obviously down (~50m or closer). At longer ranges, though, its pretty common to only get a random shot into someone unless you're sniping (and when sniping you typically don't aim for the head). The reason for this is that its hard to put rapid shots right on top of one another farther out than about 150m when you've been running around and breathing hard and you're not in the best firing position. And people don't tend to hold still (though sometimes folks do sort of get "caught in the headlights" and freeze). For these reasons most longer-range fire is suppressing fire, not lethal fire. You are trying to fix the enemy in place and distract them with your shots while the rest of your side maneuvers (to assault or break contact). With your medical tech dying under such circumstances would just be horribly unlucky. On the other hand, if the characters in the story aren't trained fighters they will be much more likely to not really engage in suppressive fire to begin with.
Unlike the movies where the James Bond calmly pops a bad guy in the face with a .380 and then just stops paying attention to him because he's 100% confident he's done, you can hit someone in the face (the cheek, say, but not into the nasal cavity straight-on) with fully jacketed small caliber pistol bullets (.45 ACP, 9mm, etc.) and the bullet may slide off the bone below the brain case and out the right or left side of the base of the back of the neck. That never happens in a cool-guy movie, but its the reason that in real close quarters gun fights you never fire just once and always re-index your targets -- and sometimes follow the shooting up with physical kicks, stomps, heavy objects, etc. to make sure that business is properly handled. (Btw, fully jacketed pistol bullets are some of the worst for actually killing people, which I've always felt was sort of cruel to both parties.) This gets back up to the correlation between the proximity of an engagement and its probable lethality. This stuff happens very quickly -- 10 seconds in this environment is a very long time.
But traumatic injuries never cease to amaze
What is surprising about gunshot wounds is not what will obviously kill (zombie rules apply: kill the brain) but how often minor-seeming wounds tend to turn out being fatal if not immediately treated (a shot through the upper arm or leg that doesn't seem to bleed much) and how often rather catastrophic-looking wounds turn out to be OK if handled properly (the classic guts-in-his-hands situation when no severe arterial bleed is occurring).
In the real world we have what we call "the golden hour". People who live past this hour stand a very high chance of survival, as long as infection does not take them (hence those pills mentioned earlier). This balance will be shifted considerably in a world with miraculous medicine.
Stats update
I would like to give some concrete numbers instead of simply the "it depends" answer with regard to statistical impact on survival rates, but... it really does depend on quite a few factors. Trying to pin down epidemiology statistics for combat wounds isn't too hard for a specific American war (good luck with any others), but I'm not quite sure these wars are representative of your proposed environment. If this medical technology were prevalent it maychange the way we fight war. If it were not prevalent, but rather monopolized by one side then it would certainly change the way that side fights. (Or not. Sometimes the side with the super-weapon is bogged down in old doctrine and bureaucracy. Japan invented the dominant naval weapon of WWII, the aerial torpedo, yet stuck with their (highly successful and very well drilled) ship-to-ship night fighting doctrine long after the Americans had found ways to avoid it and had themselves turned their focus to naval aviation. Oops!)
Above I mentioned that proximity is a big factor in delivering catastrophic shots. How common this situation is will greatly influence the prevalence of sudden fatalities. In open terrain the odds of close encounters is much lower (near ambush aside, of course, but without concealment near a route far ambush is much more likely -- but consider the terrain: temperate forest, desert, mountains, island/beach, jungle, urban, the moon, etc.). With this in mind, if the enemy has no air or artillery (because those could be catastrophic no matter how great your medical skills are) infantry commanders may feel justified in making bold, overland movements in broad daylight knowing that the odds of death or even long delay in the event of a far ambush conducted with small arms are quite small. Movement is really the heart of how combat actions go down, not the shooting, so this could be a very significant change -- even in urban environments. Snipers would be forced to start shooting for the head, and thus becomes dramatically less effective, etc.
All that said, a firm statistic on OIF/AEF combat injuries is 30~35% of combat wounds are to the head or neck. In your world this means that at least 65% of other combat casualties are non-fatal (not all head injuries are fatal; a significant portion of those are eye injuries due to flying debris -- wear eye protection!), and the majority of those should be situations where the wounded soldier continues on mission (depending on whether limb regeneration and/or a lengthy recuperation period is part of the deal).
A twist to this may be that if the medical technology is so efficient that guns wounds become relatively ineffective, you can rest assured that infantrymen will get creative. They will begin rigging huge demo ambushes, abandon rifles for grenade launchers, abandon knives for swords or hammers, running the enemy down in cars, etc. Higher command would likely switch to chemical weapons or shift their budgets around so that infantry are treated like forward observers and the real fight is artillery and air, etc. The show will go on and this change will have a tactical impact on how that change manifests. It very likely would not have a strategic impact, though, unless only one side were in possession of the technology.