Thanks to a large expatriate community and a good flow of Japanese tourists, Cebu has an inordinately large number of Japanese restaurants, which is great. Unfortunately some of them are fake, or rather not authentic. These - mostly, it must be said, Chinese-owned businesses - are aimed primarily at the local clientele interested in the health benefits of Japanese cuisine, rather than Japanese nationals, and the food is awful. Mikado, Saisaki, Ginza, and I Love Sushi are good examples of putative Japanese restaurants to avoid; their food is about as Japanese as a Chinese girl in a bathrobe.
In addition, there are a few small eateries operated by Filipina girlfriends being kept busy by their Japanese sugar daddies, who seem to think that the names of a few Japanese dishes on the menu will draw in customers. The food in these places is inedible.
Because of the large number of Japanese and so-called Japanese restaurants, I've selected only the best. These are, inevitably, owned and/or operated by Japanese expats. Unfortunately you pay for authenticity and quality with a few years of your life; the Japanese are incurable nicotine addicts and all authentic establishments are full of second-hand smoke. But, in most cases, it's worth it.
The best without question is Yumeya Kihei, which used to be in the Cebu Plaza but transferred to F Cabahug Street - right across Ocean Wok - when the Plaza went belly-up in 2003. Yumeya Kihei is the best Japanese restaurant not only in Cebu, Japanese expats agree, but the entire Philippines. The chef is the owner and he pays careful attention to all details, and, judging from his girth, doesn't skimp on the tasting. Although the standards of service are local, the food is world-class. In fact, the Manila-based Japanese Ambassador to the Philippines has told Wa'y Blima! that Yumeya Kihei is the best Japanese restaurant not just in Cebu, but the entire Philippines. Now, all this quality doesn't come cheap. You'll be paying something quite close to first-world prices for your dining experience at Yumeya Kihei.
Even more expensive than Yumeya Kihei is Kaishu, located near the Shangri-la in Mactan. The emphasis here seems to be on fresh ingredients flown in from Australia and Japan. Kaishu has recently been trying to add the local rich folks to its clientele, with some success.
An excellent Japanese restaurant is open 24 hours, but the quality drops during the night. Han-nya is owned by a Mr Watanabe, and is located inside Hotel Asia, also owned by Mr Watanabe; recently he opened a Japanese-style barbecue on the roof, which - for some reason - serves Filipino dishes along with the barbecue. It sounds weird but the ambience and the food are both great and well worth a visit.
Another favorite among Japanese expats is Senryu. This is owned by a Filipino businessman whose wife is Japanese, who hardly ever leaves the shop floor. The food is quite good but service can be extremely slow when the expats have booked one of the function rooms upstairs. Senryu is right across the Golden Cowrie; if you find the parking lot full, better cross the road.
Kyohei, on A S Fortuna, is a good place for grilled Japanese delicacies. When the owner is around - which is most of the time - the food is first-rate.
For the budget-conscious, there is Rai-Rai-Ken, a moderately priced chain of Japanese restaurants that is popular with expats and locals alike. The name implies that the noodles are good, and they are - and so is almost everything else on the menu. Try the wasabi shake for an exotic treat found only in Cebu. Rai-Rai-Ken are located in the malls, and are thus the only non-smoking Japanese eateries I know of.
An even better place to get noodles is Ramen Kamekichi, located on F Cabahug near the Kartzone. The Japanese owner and cook will prepare your noodles as you wait on the other side of the counter. Kamekichi's joint has long been a favorite haunt with homesick Japanese expats who drown their sorrows in glass after glass of diluted Japanese liquor. Unfortunately the restaurant is closed on Sundays.
There are a couple of Japanese restaurants in Mactan, also operated by Japanese expats, which are rated highly but which Wa'y Blima! hasn't tried: Rokumeikan, along the Marigondon Road, and Daruma, in Pusok, central Lapu-lapu City.
By the way, the Japanese restaurant in the Waterfront, Kanchiku, is overpriced and the quality is substandard; you may wish to avoid it.