First, the question "shouldn't it" is something of a value judgement, particularly in a show with made-up science. A set of creators can easily agree that water, for the purposes of Stargate operation, is considered equivalent to air (which, it must be emphasized, also usually fills the Stargate's event horizon when it's activated), and that blocking an event horizon requires material that is in a solid state. As long as it's consistent within the show, this is a perfectly valid approach.
The evidence we've had suggests that a gate being underwater is NOT the same as burying the gate, or at least, not always. It's certainly possible that once a certain depth/pressure is reached, it does count, but that's never explicitly addressed.
One possible counterexample to this theory is that in the season 3 finale "Nemesis" the original Stargate is lost at sea at the end, after being used to escape Thor's ship. The next episode, "Small Victories," begins with the rest of SG-1 (save Daniel, who was already on Earth) finally returning home, now that the second Stargate was in place and functional at the SGC (and dialogue points out that they were having trouble getting it working). Jack complains that they've been dialing for a week. Now, this could be taken as evidence that the gates were considered 'buried' until this time. However, that doesn't entirely track with the facts as presented... if the first Stargate is out of commission, it should probably have jumped to the second automatically without setup. There is a question of gate-primacy, but that only seems to matter when both gates are functional. If the Egyptian gate was considered blocked by the water, the only issue would be unsealing the second Stargate. They might naturally be loathe to do this until all the defenses like an Iris were set up, so unfortunately it's not conclusive evidence that the first gate was still actively receiving dial-ins while underwater... nor is the fact that SG-1 had been trying to dial for a week, because they don't actually mention whether they tried dialing for a week and got no response on their GDO (which might suggest the gate is active but under water and so it would not be a good idea to try returning home) and they were waiting until they were sure the second gate was hooked up and "primary", or if they simply got no result at all and were waiting for any response. We do know the Russians hadn't found it and sealed it themselves by that point (because in "Watergate" the search was described as ongoing when a part of "Small Victories" occurred), but we never hear what state the Stargate was when they found it (it could have settled on a rock formation that happened to block the gate, which would render all of Earth inaccessible until the Antarctic gate was opened).
So, lacking any conclusive evidence to the contrary, based on "Watergate" and "The Shrine", we have to assume the gate does NOT consider "underwater" to be blocked, at least at certain depths.
Now we can attempt to look into how it all works within the technology of the show.
Because it's not been explicitly addressed to my knowledge, here we must necessarily get into speculation, but it is at least informed speculation. Leaving aside deliberate intentions that might have gone into designing into the Stargate system (they might anticipate wanting to link to worlds where water-based life is found, for example, but not places where the Stargate is deliberately buried) and focusing on the mechanics alone, there is some evidence that the Stargate tries to move material out of the way prior to forming a wormhole.
As we've already pointed out, air fills the event horizon, and yet doesn't count as the gate being "blocked." Furthermore, we see one particular notable example that pertains to this... in the very first episode!
From the transcript:
SMOKER: Trust me. Nobody ever comes down here but us.
Behind the tarp, something stirs ever so slightly. The female officer notices, and starts in surprise.
WOMAN: Does that thing always do that?
DEALER: (not looking up from his cards) Do what?
WOMAN: Whatever it is under the tarp! I just... (glances back at it briefly) saw it move or do something!
SMOKER: Probably the only thing it ever did was cost money.
DEALER: Yeah, it looks like they ran out of that. Been shippin' personnel out of here for months.
Again, something shifts beneath the tarp, the movement more noticeable than before. The woman is the only one to notice, however.
WOMAN: I'm telling you, that thing is moving!
SMOKER: (removing the cigar) If you don't have the straight, just fold.
Instead of answering, she gets up from her chair to investigate.
DEALER: Can we take that as a fold?
She ignores them, moving slowly and cautiously up the ramp towards the Stargate. Behind her, the others resume their game.
SMOKER: (off camera) Just finish the hand. She's out.
As the female officer gets halfway up the ramp, the covered Gate creaks somewhat. She takes two more steps, and suddenly the ramp starts shaking, the railings groaning and creaking under the tremor. Immediately, she backs away. The poker table is shaking as well, the chips and cards scattering. The other four officers get to their feet as their comrade stumbles to the bottom of the ramp, nearly losing her balance entirely. Cut back to the Gate. The tarp is rippling and billowing like water, and starts to slide away. As the Gate starts to spin, the tarp is fairly blown off of the Gate, tossed into the air and slipping to the floor. The officers watch in shock as the Stargate continues to spin, the chevrons locking in place.
As you can see by watching the episode itself, there is a definite motion of air moving through the Stargate, before it's activated, before it even begins spinning (spinning is loud enough that more than one soldier would be able to notice it). And the force of the air is, at one point, enough to blow the tarp off. It's likely in most other cases, this puff of air would not be noticed, or mistaken for a pickup of wind, but restrained under a tarp, it's visible.
This outward force may be a first step of the gate's handshaking protocol, to determine if the gate is "blocked." Can whatever material blocking the event horizon be moved freely with a slight push, generated by whatever mysterious technological forces the gate can employ? If it can, the gate attempts to start dialing-in (though it may still be blocked by other things like an outgoing connection completing before the dial-in). If it can't, the gate is marked "out-of-service" and the dialing doesn't even get started on the other side (a buried Stargate doesn't seem to glow or spin as other Stargates do when people attempt to dial in).
Water, like air, is relatively simple to move out of the way and perhaps a slight vaccuum is deliberately formed at the event horizon at the moment the wormhole is established. Rocks and sand and other solid obstructions require more force to move (which should be obvious, you can swim easily in 6 feet of water, but buried in 6 feet of soil you'd be virtually unable to move), presumably more force than the gate is designed to be able to clear. Again, at a certain depth the pressure of the water may be too great, or in certain configurations (a gate horizontal on the bottom of the ocean, for example, where the gate's natural clearing-mechanism would be attempting to push water "down" where there's nowhere for it to go, might be more work than pushing it up or sideways).
Whether this limit's a fundamental one to wormhole technology (like the 38-minute limit, barring rare exceptional cases like a black hole or intelligent energy-water), or a design decision doesn't matter much, but, to me, this makes sense as an intentional design feature. The unstable vortex can completely disintegrate any material it comes in contact with, and the ancients had other technologies that could clear solid material in various other ways... it stands to reason that if a Stargate designer wanted to, they could make "clearing the event horizon on the other side" stage one of any Stargate dial-in and never have a gate be blocked. Of course, that's extremely rude to people you might plan on visiting one day, to give them a gateway where you can enter their land at any time and there's nothing they can do about it unless they happen to have figured out Iris/Shield technology, and even then you can keep dialing in and bothering them with unsolicited radio messages informing them that you're an Atlantean prince trying to smuggle your vast fortune to another planet and they'll get a hefty share if they help you.
One last thing needs to be addressed: In "The Shrine," Shepherd does indeed suggest that the gate room would be flooded if the shield was open. As you point out, this is not correct, either the gate would keep the water from flowing in at all, as in Watergate, or it would already be flowing through the gate and be destroyed by the shields only on the other side, draining the flooded area pretty quickly. However, since "blocked by water" is a rare enough set of events, it's reasonable to assume that Shepherd either was unfamiliar with or momentarily forgot that characteristic (or knowing that the gates were slightly different in Pegasus, he decided to err on the side of safety). The gate did continue to be held open for 38 minutes, but that could easily have been because some long vine, for example, wrapped around one edge of the gate, unable to completely cross but inside enough to prevent the gate from shutting down until the time limit.
