My GG grandparents listed Riga, Russia (now Latvia) as their last residence on ship manifests and they imm at two seperate times listing Riga on both manifests --August Herrmann in 1898 with his sister, then his wife and kids in 1901. (It is interesting, though, that both groups sailed on the same ship!!- the Patricia.)
I assume they were in Riga because of the town's ports on the Baltic Sea, catching ship to Hamburg, then on to NY. Hamburg is a fair distance from Kibarty and traveling that distance overland was probably too expensive. It is doubtful that the wife & children lived in Riga for the two years between sailings, so stands to reason that this route was a common one from Kibarty.
Regarding church records- Considering that your ancestors were German Russians, do you know how long they were in Russia? Maybe you are not having luck with the records because the family wasn't there very long?? Also, if you haven't done so, consider researching the brothers and sisters of your ancestors if you can find them. The ship manifest for the BROTHER of my August Herrmann's wife lists his German town of birth! as well as his father's name and residence in that same German town!! So, I know that my GG grandmother was only in Kibarty for probably less than 25 years (long enough for her children to be born there, though!).
That being said, checking Suwalki town is not a bad idea, but also consider any close large town (other than Wirballen as you already ruled that out!)