An algorithm that guarantees correct answers but has random runtime that may even be unbounded is called a Las Vegas algorithm.

https://en.wikipedia.org/wiki/Las_Vegas_algorithm