I'm surprised you say Fukuoka is off the beaten path since it's like the biggest city in Kyushu with international airports, schools, and whatnot. Was it not a popular destination for foreigners back when you were there? I know it's always been a popular spot for Japanese people.
Do you know if the shop is still around?? I might be going for work next month, and I'd love to get some good shawarma.
The fact that it keeps me off Reddit is a huge plus.