OK, I don't have time to answer this as I want to. My background is in psychology, and I fell into role playing games when I turned 10 in 1976. So by the time I was in college, understanding where the term Roleplaying game really came from, I understood the critical nature of immersion, how it is the most important ingredient for game success.

And to be clear, the definition of immersion is to "Immerse oneself into the identity and Role of the part one is playing. To respond, as much as possible, as the person one is playing, not as oneself."

And before getting into the smaller details, I will dive right into the fact that the very system/game one chooses has a huge amount to do with the amount of Immersion.

Metagaming is the opposite of immersion. You use both terms, but I need to make that absolute definition from the beginning. This also means rules that encourage metagaming decrease the immersion in a game and therefore, decrease the main ingredient of a roleplaying game. The mechanics are called "Dissociated Mechanics", a term coined by Justin Alexander. This is very worth reading, because it gets into many of the larger picture issues with players being able to use in-game logic to see the world around them, as opposed to the rules forcing dissociation from in-game logic.

Once the players assume that rules are going to determine the content of an encounter or treasure (based on EL, or whatever) instead of what the environment or history of the area dictate, verisimilitude is lost.

Vreeg's Rules of Setting design are also heavily immersion related. My current campaign is 26 or so years old (started in '83). Building verisimilitude is a huge part of this.

• Vreeg's first Rule of Setting Design
  Make sure the ruleset you are using matches the setting and game you want to play, because the setting and game WILL eventually match the system.

  • Corollary to Vreeg's First Rule
    The proportion of rules given to a certain dimension of an RPG partially dictate what kind of game the rules will create. If 80% of the rulebook is written about thieves and the underworld, the game that is meant for is thieving. If 80% of the mechanics are based on combat, the game will revolve around combat.

    • Multiply this by 10 if the reward system is based in the same area as the preponderance of rules.

  • 2nd Corollary
    Character growth is the greatest reinforcer. The synthesis of pride in achievement with improvement in the character provides over 50% of the reinforcement in playing the game. Rules that involve these factors are the most powerful in the game.

• Vreeg’s Second Rule of Setting Design
  Consistency is the Handmaiden of Immersion and Verisimilitude. Keep good notes, and spend a little time after every creation to ‘connect the dots’. If you create a foodstuff or drink, make sure you note whether the bars or inns the players frequent stock it. Is it made locally, or is it imported? If so, where from? If locally made, is it exported?

• Vreeg's Third Rule of Setting Design
  The World In Motion is critical for Immersion, so create 'event chains' that happen at all levels of design. The players need to feel like things will happen with or without them; they need to feel like they can affect the outcome, but event-chains need velocity, not just speed.

• Vreeg's Fourth Rule of Setting Design
  Create motivated events and NPCs, this will invariably create motivated PCs. Things are not just happening, they happen because they matter to people (NPCs). There is no need to overact, just make sure that the settings and event-chains are motivated and that the PCs feel this.

• Vreeg's Fifth Rule of Setting Design
  The Illusion of Preparedness is critical for immersion; allowing the players to see where things are improvised or changed reminds them to think outside the setting, removing them forcibly from immersion. Whenever the players can see the hand of the GM - even when the GM needs to change things in their favor - it removes them from the immersed position. (Cole, of the RPGsite, gets credit for the term).

Remember that part of immersion is the lack of feeling walls around and rails under the characters. This means that the players should not feel that there are things that their character cannot do solely because of the rules or the GM's mindset. The job of the GM is to enable roleplay, not to inhibit it. This also means the GM must be as immersed as the players, or more.

Another big-picture thing that may irk some folk who sell stuff is that published settings can hurt immersion. They don't destroy it; but when the players have a lot of knowledge about a setting that their character would not have, this increases the opportunity to use it, consciously or unconsciously. Similarly, if your setting has its own bestiary that the characters learn as they go along, or at least a lot of homebrew tweaks, the players get used to working with the in-house data and not trusting the published sources.

If you have done all of this larger-scope stuff, the smaller scope stuff becomes easier. As a GM with miles on the tires, I find that playing up the level of knowledge my NPCs might have and do not have helps keep the players in the same mindset. Players key heavily off the way the GM plays their NPCs. They won't do the funny voices or the mannerisms if the GM does not, and if the GM is particularly careful about what their NPCs know and don't know, especially verbally, the players emulate this.

Define the Consequeces of Success and Failure Up Front

This answer addresses a very similar question. I think everything I said there applies equally here. In short: if you explicitly define the consequences of success and failure, players are less likely to misunderstand the information and run off doing some nonsense.

Let It Ride

In your case, there's one other trick I would add, shamelessly lifted from the RPG Burning Wheel:

A player shall test once against an obstacle and shall not roll again until conditions legitimately and drastically change. Neither GM nor player can call for a retest unless those conditions change. [The results of] the initial roll count for all applicable situations in play.

In other words, say you roll to search a room for stuff. You get an 8. That's it. That's your result for searching the room for stuff. If you retry the action, you don't reroll. If you try a new action, too bad, you're not gonna gain anything more. Likewise, if I roll 15 to climb a cliff, that applies to the whole climb; the GM can't ask me to reroll every 10 feet or anything stupid like that.

Let It Ride makes sure that rolls actually matter — you can't just turn a round an immediately invalidate something with another roll. Beyond that, it keeps the game moving forward. When we know that each and every result will stand, we can all focus on moving forward incorporating the result.

If you can't abide by a success or failure outcome, then don't put it on the table at all. Manufacturing excuses to reroll until you get the results you want is a sign that you need to rethink how you're scoping consequences. It's possible you shouldn't be asking for a roll at all.

If you want a situation to be a series of rolls, break it up into discrete tasks instead of just rolling amorphously a couple of times and then handwaving that, okay, now this one counts.

Call Them Out

If your players are constantly asking for rerolls, try just calling them out on their weaseling. Like, just straight-up say, "You're trying to weasel out of the outcome we already rolled for. Let's move on."

Why Are Your Rolling for "There is Nothing Here" Anyway?

If there's nothing to find, what's the roll about, anyway?

Occasionally there's some payoff to roll-to-find-out-if-you-know-that-nothing-is-here as a form of information-hiding, but from what I've seen, a lot of GM advice defaults to "Roll for everything just to create fake tension!" way, way too much.

In the example given, I'd only ask for a roll if I could frame it as something like one of these:

• "If you succeed, you find everything of value in this room — secret passages, treasure, clues, everything." That way the PCs can discover something for their efforts even if it's not what they necessarily intended to find.

• "Okay, so, time is of the essence, right? If you succeed, you find out right away whether there's a trap door here. If you fail, it'd take a long time to search properly." Now the roll is all about "What is the cost of the information you want?" I do this only when there is already pretty obvious pressure of some sort; otherwise you're just kinda manufacturing complications that don't really matter.

Otherwise I'd just tell 'em. There's very little down side to doing so. What's the point of trying to maintain a feeling of uncertainty here, unless you're trying to waste time on purpose?