A deterministic algorithm for exploration.
Other answerers have already created solutions for what to do if you have an algorithm that will return you back to the start (and "move randomly" theoretically does indeed do that with probability 1) - but what if you're not capable of producing random numbers? A computerized PRNG has a finite length after which it will repeat values, so a maze with a pathologically chosen size could be designed to trap an explorer dependent on a particular PRNG in an infinite loop.
If you have perfect memory, you can use the following algorithm instead:
Consider each room that you have visited so far as an ordered pair of numbers (n,m) where n is the number of teleporters in the room and m is the number of the teleporter which you took. Keep track of the entire sequence of rooms that you have visited. When you arrive at a room, choose a door which creates the shortest new sequence that is not a repeat of any sub-sequence the previous traversal.
Since we're incapable of producing random numbers, if there are multiple possible doors which would all produce minimal new sub-sequences, choose the one with the lowest number.
A worked example
Let's assume (as a worst-case of this algorithm), that you are in a maze where every room has the same number of doors. Let's say 3.
- In the first room, you choose door #1, because the sequence is empty. The traversal is now [(3,1)]
- In the second room, (3,1) would be a repeat but (3,2) has never been seen before, so you choose door #2. The traversal is now [(3,1), (3,2)]
- In the third room, you choose door #3. The traversal is now [(3,1), (3,2), (3,3)]
- In the fourth room, all of (3,m) have been seen, but the subsequence [... (3,3), (3,m) ...] has never been seen before for any m, so you choose door #1 since it has the lowest number. The traversal is now [(3,1), (3,2), (3,3), (3,1)]
- In the fifth room, all of (3,m) have been seen before, and so has [... (3,1), (3,2) ...], so you choose door #1 again to form [(3,1), (3,2), (3,3), (3,1), (3,1)].
- In the sixth room, you choose door #2, because [... (3,1), (3,1) ...] has already been seen, but [... (3,1), (3,2) ...] has not.
Any exploration must either explore the whole maze or get caught in a cycle. Thus, it is sufficient to prove that this algorithm will never get caught in a cycle.
I believe it should be possible to prove that if this algorithm traverses a cycle of length k, it guarantees that at some point in the future, there will be a sequence of k steps in the future which is not a repeat of the k steps immediately before it, which will therefore not repeat the cycle, (unless the maze has only one room and one teleporter, in which case this algorithm has already explored the whole maze). However, I don't have a proof of this.
Other sources of randomness
The guaranteed exploration from this algorithm comes from its property of non-repetition. True randomness has this property as well (it is capable of producing sequences not before seen), but so do irrational numbers. If there are fewer than 10 doors in each room, then choosing the n'th digit of pi modulo the number of doors in the room would also guarantee eventual total exploration, because pi does not repeat. However, this requires that the explorer be capable of calculating a decimal value of pi to arbitrary precision.
This algorithm guarantees eventual total exploration of the maze, which is sufficient to find your stone again.
The downside is that the memory requirements are exponential with the size of the maze, but that's table-stakes with the other solutions already.