Ok, I'll take a crack at the definition.
Counter: A Pokemon that beats all or most variations of another Pokemon. Capable of Switching in easily.
Check: A Pokemon that can impede another Pokemon's sweep or stall cycle, but may not always win if the opponent carries a certain move. This can also apply to moves or hazards.
You asked if it was possible for two Pokémon to both be forced out at the same time.
I personally like the definition that Pokémon A counters Pokémon B if Pokémon A will virtually always defeat Pokémon B one-on-one (barring extreme shenanigans like entry hazard overload, constantly whiffing attacks, being prevented from moving by paralysis, confusion, etc.), and Pokémon A checks Pokémon B if Pokémon A will usually defeat Pokémon B one-on-one, but Pokémon B has some certain tricks in its movepool that will allow it to defeat Pokémon A if it happens to have those tricks on hand. But what do you call the situation where Pokémon A and Pokémon B can easily OHKO each other and cannot safely switch in on each other, and Pokémon A is faster than Pokémon B and is extremely likely to win the confrontation if both are already on the field, but Pokémon A loses if Pokémon B hits it on the switch-in? My main example for this involves a fakemon of my creation, which is probably a bad idea, but it's the best example of the kind of matchup I want to demonstrate that I can think of. So, allow me to explain the matchup...Beaten? The point is the intimidation you input with the switch in. Of course you're not an absolute counter to Celebi. Which is why you're a check. You're only beat when your Pokemon has fainted, and of course that is no longer a check so the proposal of beaten counters is quite absurd.
Hence the fact the term [check] comes from chess. You're putting the opponent in a situation where he can stay in for a risk or safely switch. An absolute counter is "switch out or die".
I don't see why this is so complicated.
Check: A Pokémon that will come in not-so-easily, maybe after death fodder and threaten to out-beat the opposing Pokémon whether immediatly or proceedingly.
Counter: A Pokémon that outright threatens the opposing Pokémon with resistances, blocking strategies, set up windows and of course an easy KO.
One of the fakemon I have created, Voltran, is a dangerous Electric/Dark Special sweeper with base 160 Special Attack and base 140 Speed, but base 45 HP and base 65 Defense (it does have base 140 Special Defense, but that doesn't help it much since its base HP is so pitiful, and its base 50 Attack means it can't even try to be a mixed attacker). Voltran's extreme power and frailty means that it cannot afford to let its opponent make a move, so it goes directly on the blitzkrieg offensive with a powerful Electric-type move like Thunderbolt or Thunder (or its signature move, Lightning Surge, which hits 2 to 5 times with 75 Base Power, obliterating just about anything that's not a Ground-type... unless its 75% Accuracy fails to connect, and as I said, Voltran can't afford to let its foe make a move). For its other moves, Voltran's best options are Dark Pulse (or Dark Storm — basically Hydro Pump as a Dark-type move... and, yes, it has imperfect accuracy) and Earth Power (to deal with most of what resists its STAB moves — only Grass/Fighting, Grass/Dark, Grass/Fairy, and Hydreigon resist the trinity of Electric, Dark, and Ground); its fourth move is Dragon Pulse, Psychic, or Psyshock to deal with most of what resists the former three. (It can also run Calm Mind, but that's just begging for a physical attacker to wreck it while it sets up.) So, you are probably asking, why is Voltran relevant to its thread? The answer is simple: because it got a very noteworthy adversary in Generation VII. Enter Pheromosa, who is also frail, hard-hitting, and extremely fast — even faster than Voltran. And since Pheromosa is a Bug/Fighting type, it can effortlessly wipe Voltran out with either of its STAB options — there is no freaking way that Voltran will survive a Lunge or High Jump Kick; heck, Voltran could probably be put down with U-Turn or Brick Break. (Voltran might survive a Bug Buzz or Focus Blast, since its Special Defense is excellent, but that's undermined by its terrible HP.) However, this checkmate situation requires Pheromosa to actually get in without getting fried, which means it's relying on a sacrifice play or a tank running U-Turn (or, again, Voltran missing). It all comes down to who lands the first hit.
What do you call a matchup like that, and can you think of any other examples, preferably ones that only involve canonical, Game-Freak-designed Pokémon? (I think Pheromosa is a check to Voltran, but its inability to switch in safely despite resisting Dark and Ground makes the term somewhat inaccurate. Pheromosa also is somewhat of a counter to Voltran, as while both are Glass Cannons who can easily OHKO the other, Pheromosa's superior speed gives it the edge in a neutral confrontation where both are on the field, and likewise, while it's relatively easy for Pheromosa to come in and threaten Voltran, it's nearly impossible for Voltran to come in and threaten Pheromosa unless it has some way to close the speed gap — but, again, if Voltran hits Pheromosa while it's switching in, Pheromosa is done for.)
(You may also notice that Voltran is countered by Malaconda, whose Grass/Dark typing and high Special Defense, HP, and Attack let it laugh off whatever Voltran throws at it and OHKO it with Power Whip.)
Oh, and I did think of another example of such a matchup, albeit a somewhat weaker one: Starmie vs. Victreebel. Both have solid offensive stats and mediocre defensive stats, and both carry moves that are super-effective on the other; Victreebel can wreck Starmie with a STAB Grass attack like Leaf Blade, Energy Ball, or Leaf Storm, while Starmie can eliminate Victreebel easily with either STAB Psychic or Psyshock, or alternatively Ice Beam or Blizzard. Both can OHKO each other (at least, I think they can — I will need to run damage calculations to verify this), so neither can safely switch in on the other, but Starmie is faster than Victreebel, so if both are already in on each other, or if Starmie hits Victreebel with a Psychic- or Ice-type move while Victreebel is (foolishly) switching in, Starmie wins. If Victreebel hits Starmie with a Grass move while Starmie's switching in, Victreebel wins. (I think Victreebel may survive switching in on Starmie using a Water- or Electric-type move or Power Gem or Dazzling Gleam, but it will not survive staying in to eat the Psychic- or Ice-type attack that will be heading its way on the next round.) This is a weaker example than Pheromosa vs. Voltran because neither Starmie nor Victreebel are as ridiculously strong or ridiculously frail as Pheromosa or Voltran, so the outcome of "first strike wins" is somewhat in doubt. With Pheromosa and Voltran, it's only ambiguous that an OHKO will happen if Pheromosa is hitting Voltran with a Special attack or Voltran is hitting Pheromosa with Earth Power (though the difference between Voltran's speed and Pheromosa's speed is small enough that Voltran might be able to outspeed Pheromosa by investing more EVs and favorable Nature into its Speed, as well as holding a Choice Scarf, while no amount of min-maxing is going to make Victreebel outspeed Starmie without Chlorophyll). However, Starmie vs. Victreebel is another example of a matchup where the line between check, counter, and simple advantage is blurred by the power and frailty of the Pokémon.
EDIT: Okay, I went to the damage calculator to see if my thoughts on Starmie vs. Victreebel were accurate, since they turned out to be less offensively potent and less defensively mediocre than I recalled them being. It turns out that standard offensive Starmie (252 SpA EVs, Timid Nature, holding a Life Orb) can indeed OHKO standard sun sweeping Victreebel with Psyshock, and standard sun sweeping Victreebel can OHKO standard offensive Starmie with Solar Beam, both being 100% guaranteed. However, Timid Starmie's chance to OHKO Victreebel with Psyshock drops to 25% if Victreebel has a Defense-boosting Nature and maxed Defense and HP EVs (I'm not sure why one would go with that sort of Victreebel build, but I figured that I might as well go for the worst-case scenario for Starmie). A Modest Starmie using Psyshock on that same Victreebel has a 75% chance to OHKO. And both of these Starmie are still holding Life Orbs; swap that out for Choice Specs, and both Timid and Modest Starmie OHKO Victreebel every time. And none of these calculations have had Psychic Terrain around; with Psychic Terrain, both Timid and Modest Starmie get guaranteed OHKOs even if holding a Life Orb (heck, even a Twisted Spoon will suffice, but Victreebel might survive Timid Starmie's Psyshock if it gets any less of a boost from its held item). I haven't even looked at Ice Beam, by the way. Bulky Rapid Spinner Starmie, on the other hand, struggles to 5HKO the sun sweeper Victreebel (no HP or Defense EVs, 4 Special Defense EVs) with Scald, even without sun — being not very effective doesn't help. This isn't accounting for burn damage, by the way. Meanwhile, the sun sweeper Victreebel (252 SpA EVs, Modest Nature, Life Orb), when attacking a standard Rapid Spinner Starmie, always OHKOs it with Solar Beam unless it's raining, in which case it's a 4-turn 2HKO. But this Starmie's only extra bulk is 252 HP EVs; it has a Timid Nature and no SpD EVs. If Starmie has a Special Defense-boosting Nature and 252 Special Defense EVs, Solar Beam... is still an OHKO (2HKO in rain). Go figure. Timid Victreebel still OHKOs Starmie, though rain drops it to a 0.5% chance to 3HKO. In other words, while offensive Starmie has the edge against Victreebel, as I suspected, defensive Starmie just gets crushed.
EDIT: I was able to finagle the calculator to test the Voltran versus Pheromosa matchup (I used Blank Set Abomasnow, which Voltran is actually far lighter than, and tweaked the typing, base stats, Ability, and moves so that it matched Voltran's profile), and what I saw was surprising. Well, okay, I wasn't surprised that an Über All Out Attacker Pheromosa build could slaughter Voltran with High Jump Kick or Lunge, as well as U-Turn or Brick Break. (Low Kick is also an OHKO, even though Voltran only weighs about 50 pounds.) What surprised me was that, while Voltran's Thunder/Thunderbolt and Psychic/Psyshock (and Dragon Pulse) indeed OHKO Pheromosa, no questions asked (and Lightning Surge also wipes Pheromosa out in just one hit — heck, Parabolic Charge would be a one-hit KO), Dark Pulse has only a 50% chance of OHKO'ing Pheromosa (though it was guaranteed to leave it with less than a tenth of its HP, meaning that it would be an OHKO after Life Orb or Stealth Rock damage), and Earth Power only took off 68.9% to 80.9% of Pheromosa's HP — and this Voltran is Modest, holding a Life Orb, attacking a Naughty Pheromosa. (Dark Storm, on the other hand, is indeed an OHKO.) This means that if Pheromosa switches in on Voltran using Dark Pulse or Earth Power, Pheromosa may actually survive if it had full health beforehand; it'll be almost ready to keel over afterwards, but it'll have enough fight in it to wipe Voltran out if it doesn't GTFOOD (that's "Get The Fuck Out Of Dodge", for the curious). If Pheromosa is Lonely instead, Dark Pulse can't OHKO from full health (though it still might after Stealth Rock or Life Orb damage; specifically a 62.5% chance from Stealth Rock damage, and a 50% chance after Life Orb damage), and Earth Power only does 61.8% to 71.3% damage to Pheromosa — still a guaranteed 2HKO, but even Stealth Rock can't make it a OHKO. If Voltran is Timid, the damage on Dark Pulse and Earth Power goes down even further, though they still remain 2HKOs — but more interestingly, Voltran now outspeeds Pheromosa if it isn't running a Speed-boosting Nature, though Pheromosa still OHKOs Voltran with its physical STAB even if running a Timid Nature with no Attack EVs and not holding anything. However, Assault Vest might allow Pheromosa to survive a Thunderbolt and not be 2HKO'd by Dark Pulse or Earth Power. As for Pheromosa's Bug Buzz and Focus Blast, a 252-SpA-EV Phermosa with a Special Attack-boosting Nature could actually OHKO a Voltran with no investment in its HP or Special Defense with either move; Voltran might be able to survive Bug Buzz if it was silly enough to invest fully in special tankiness, including a Special Defense-boosting Nature (specifically, Bug Buzz would only have a 6.3% chance to OHKO), but Focus Blast would still wipe Voltran out (assuming that it didn't miss). If Pheromosa doesn't invest quite as much in its Special Attack, Focus Blast may be barely survived (but Stealth Rock and Life Orb would certainly finish Voltran off). Voltran certainly will never care about the standard Uber All-Out Attacker Pheromosa's Ice Beam in any scenario, and Rapid Spin is much too weak to give even Voltran any trouble. Of course, if both Voltran and Pheromosa are fully focusing on their offensive potential (which is what they most definitely should be doing), then, yeah, whoever strikes first will in all likelihood OHKO the other, and that's most likely going to be Pheromosa unless it's trying to switch in on Voltran.