What is wrong with "Who did John believe the man that kissed arrived?" in sentence processing terms" Compare to "John believed the man that kissed Mary arrived."
Any way that you try to write this will be pretty clumsy. But the problem with your original is "kissed arrived" in that order.
Who was it that John thought that the man who had arrived had kissed?
Who did John think the man who just arrived had kissed?
John thought that the man who just arrived had kissed who? (And you must used a rising inflection here to make it a question.)
In reality, you'd probably say something like "That guy who just arrived... who was it John though he had kissed?"