Since 5 days ago my highest rated gig have lost his place in search. Even if you work hard to maintain a great rating (my gig have 1k+ positive reviews) your place in search is not assured. Even if you search using the filter for high rated gigs, you will find gigs with 1 or 2 reviews sitting above gigs with great ratings.
While I agree that search doesn’t seem to work as well as I would like either, I’m not sure that what you are seeing with your gig is a bug. Fiverr actually does not guarantee that gigs will appear in search at all, and ranking does not generally stay the same. Gigs can shift up and down rapidly according to delivery speed, keywords and tags, competition that fits whatever algorithms are in use, etc.
The category your gig is in and exactly what you sell can affect ranking too, as the Editors put emphasis on some gigs over others. The category you are in has had a lot of problems in search. Since Google is a 3rd party site, your gig can be shifted or dropped according to changing editorial focus on Google-related gigs. (This is true for other gigs related to 3rd party sites too, like those relying on Facebook, Twitter, Amazon, etc.) If you think that your gig is incorrectly listed in search, a ticket to Customer Support is the best action.