Can I use Wally or Evosoda on a Snorlax to search my deck, even though there is {currently} no evolution of Snorlax?
No, there has to at least be the possibility of a valid evolution in order to use this card. Sorry.
Source: TPCi Rules Team (2018-07-26)
Can I use Wally or Evosoda to search my deck for a card that is not in the current tournament format? For example, could I use it on Raichu to search for a Raichu BREAK after it rotates out?
Yes, you can. Even though a card may not be in the tournament format it still exists and can be searched for even though it is known to fail.
Source: TPCi Rules Team (2018-07-26)
If I use Evosoda to evolve my Basic Pokemon into a Stage 1, can I then use Wally to further evolve it into a Stage 2 on that same turn.
Yes, but be careful of the order in which you play the cards. Wally says you can use it on a Pokemon that was put into play this turn, but Evosoda says you cannot use it on a Pokemon that was put into play this turn. So you can play Evosoda first then Wally, but you cannot play Wally then Evosoda (on the same Pokemon, of course).
Source: TPCi Rules Team (2017-03-16)
Can I use Evosoda on a Caterpie the first turn of the game or the turn that Caterpie is played since "Adaptive Evolution" says it can evolve in those cases?
No, you can't use Evosoda to evolve in either of those conditions because the text on Evosoda specifically prevents it.
Source: TPCi Rules Team (2014-05-29)
Can I use Evosoda to search for a Mega Pokemon?
As long as it evolves from the Pokemon you choose, yes.
Source: XY FAQ (2014-02-06), TPCi Rules Team (2014-02-06)
If a Basic Pokemon was put into play last turn, can I use Evosoda on it twice to bring it all the way to a Stage 2?
No, you cannot. When you evolve a Pokemon it is a new Pokemon, and since it was put into play this turn you cannot use Evosoda on it until next turn.
Source: XY FAQ (2014-02-06), TPCi Rules Team (2014-02-06)