A black hole immersed in a rotating universe, described by the Gimon-Hashimoto solution, is tested on stability against scalar field perturbations. Unlike the previous studies on perturbations of this solution, which dealt only with the limit of slow universe rotation j, we managed to separate variables in the perturbation equation for the general case of arbitrary rotation. This leads to qualitatively different dynamics of perturbations, because the exact effective potential does not allow for Schwarzschild-like asymptotic of the wave function in the form of purely outgoing waves. The Dirichlet boundary conditions are allowed instead, which result in a totally different spectrum of asymptotically Godel black holes: the spectrum of quasinormal frequencies is similar to the one of asymptotically anti-de Sitter black holes. At large and intermediate overtones N, the spectrum is equidistant in N. In the limit of small black holes, quasinormal modes (QNMs) approach the normal modes of the empty Godel space-time. There is no evidence of instability in the found frequencies, which supports the idea that the existence of closed timelike curves (CTCs) and the onset of instability correlate (if at all) not in a straightforward way.