First a couple of comments:
- Humans keep on debating over the existence of a Strong AI, long after they invented it.
Some argue that this already happening: A pocket sized computing device (namely the iPhone equipped with Siri) with which you can have conversations and ask for directions, or a large scale system (Google) which can give us answers to questions that were asked using unstructured natural language queries, would have been considered successful AI (if not strong by John Searle's definition) by most CS researchers in the 1940s and 1950s.
- Humans build Strong AI for some trivial task (for example: building paperclips) [...] The Strong AI doesn't care whether humans recognize it as a Strong AI, most likely because it was programmed to build paperclips, and trying to convince humans that it is a 'Strong AI' doesn't actually help it in its goal of building paperclips. So it says nothing.
This is by definition NOT Strong AI, it can only be strong AI if it has general problem solving abilities regardless of context. See this discussion for example by Hilary Putnam (it is somewhere toward the last third of the video): What distinguishes the human brain from even the most powerful current computer is that the human brain can solve problems it was not designed to solve. Assuming that human brains were programmed by evolution for specific purposes - hunting, reproducing, avoiding predators, etc ... - they are now capable of solving problems far beyond their original design, such as mathematical models for cosmology or composing and preforming symphonies, etc...you are explicitly defining an AI which doesn't do that, so it can't be Strong AI.
That being said, your question in general still holds, and I will address two separate aspects of it
- Can we recognize the existence of a Strong AI after it is created?
From one point of view this is really a technical question: What tests do we have for recognizing Strong AI? There is of course the Turing test and its variations. The Turing test has its problems. There have been since then other proposals for tests, such as Winograd Schemas, The Lovelace test, and others. Your question in one way reduces to a technical discussion of which one of these tests is the right one, and then how to convince people that this test is, and is one to be resolved by further research in cognitive science more so than a philosophical discussion.
Keep in mind that even once the philosophical and scientific communities arrive at a consensus on what a legitimate test for strong AI is, and then computer engineers proceed to build such a strong AI, there will always remain people that are unconvinced. After all, the scientific consensus is that the Earth is billions of years old, yet many people still believe that it is only 6000 year old or so.
Of course in the case of strong AI, there is a chance that such an AI will, in true Matrix-Skynet fashion, enslave us and become our overlord, and most people would then be convinced the hard way that Strong AI is possible.
- Or would it is possible, as soon as Strong AI exist, that humans immediately come to a consensus that it does exist?
From another point of view, the question is a metaphysical one. What you need to understand about John Searle's Chinese Room argument and the Philosophical Zombie argument is that they are not technical arguments against Strong AI, but metaphysical ones. What such arguments try to prove is that no matter what a computer or a robot can achieve, it will never have mind, only the appearance of one.
John Searle, with his Chinese Room argument, is trying to how that a digital computer can only simulate human intelligence, because it will always lack an understanding of the information that it is processing, it has no way of knowing the meaning of the symbols it processes. He calls this the syntax is not semantics argument. Searle does concede that if we were to produce a biological artificial intelligence (using cloning or some other biological replication technology), such an entity would indeed posses strong AI.
Similarly Zombie arguments try to show that something can have all of the outward appearance and behavior of an intelligent human, yet it can still be missing the first person subjective experience that characterizes humans. Such a Zombie would talk and walk like a normal person, but there would be nothing inside that it is experiencing the world or experiencing emotions. Presumably, human like AI would fall into this category of being, and therefore would not be considered to have a real mind.