Preamble
Personally, I think this question should probably have remained closed, since your main question:
"Why did Japan never “apologize” enough for World War 2?"
appears to be fully answered by the Wikipedia article you cite, and would thus appear to be too basic under the normal rules for this site.
That article also implies an answer to the "second question" you mention (which has actually been edited out of the question in its current version):
"... what prevented Japan from issuing a 'perceived as sincere' apology long ago ..."
but other answers to this question are also possible.
However, those answers are likely to be primarily opinion-based since you have not specified by whom that apology would have to be 'perceived as sincere'.
Questions to which the answers are likely to be primarily opinion-based are also off-topic for this site.
However, since the community has voted to un-delete and re-open the question, I will try to answer it.
Answer
The Wikipedia article you cited includes a section titled Controversy. This section appears to answer your main question, and at least imply one answer to your supplemental question.
To take the specific example of Japanese Prime Minister Shinzō Abe's 2006 apology, the Wikipedia article notes that:
In October 2006, Prime Minister Shinzō Abe's apology was followed on the same day by a group of 80 Japanese lawmakers' visit to the Yasukuni Shrine which enshrines more than 1,000 convicted war criminals. Two years after the apology, Shinzo Abe also denied that the Imperial Japanese military had forced comfort women into sexual slavery during World War II . In addition, Prime Minister Abe claimed that the Class A war criminals "are not war criminals under the laws of Japan". He also cast doubt on Murayama apology by saying, "The Abe Cabinet is not necessarily keeping to it" and by questioning the definition used in the apology by saying, "There is no definitive answer either in academia or in the international community on what constitutes aggression. Things that happen between countries appear different depending on which side you're looking from."
[Citations for these assertions are included in the original article.]
It is, perhaps, unsurprising therefore that many felt that apology to be insincere.
Now, consider the hypothetical situation where Germany had maintained an official shrine to Nazi war-criminals, and that a large group of members of the Bundestag had visited that shrine shortly after the German Chancellor had issued a formal apology for atrocities committed during the war.
Imagine that a couple of years later, the German Chancellor had also then denied that some of those atrocities had actually occurred, and argued that in any case, those war-crimes were not actually 'crimes' under German law.
Do you think that people would have believed the original official apology to have been sincere under those circumstances?
Of course, Germany did not maintain such a shrine, and no German Chancellor has made statements of that kind, but considering this hypothetical situation illustrates why many people felt that apologies by the Japanese government may not have been wholly sincere.
When it comes to your supplemental question, I would say that in my opinion the passage quoted from the Wikipedia above also provides an answer.
The mention of the lawmakers' visit to the Yasukuni Shrine in October 2006, and Prime Minister Abe's later comments suggest that a significant number of Japanese lawmakers do not believe that the war-crimes were, in fact, war crimes and so no 'genuine' apology is therefore necessary.
Now, in reality, for most practical and diplomatic purposes, most western governments have long accepted the public apologies from the Japanese government. Trade and diplomatic relations have been normalised for decades.
This does not, however, mean that all the citizens of those countries have accepted those apologies.
I have had the privilege of meeting with, and talking to, a number of veterans who served in the Far East during the Second World War over the years. Most are now dead, but none (to my knowledge) ever accepted the various apologies offered by Japanese governments.
In particular, during the 1990s, when the question of reparation payments was being discussed, more than one expressed their opinion to me that no sincere apology could or would ever be made.
My mother lost two brothers during the war. One was killed at Dunkirk, the other died in Sandakan Camp in Borneo (modern Malaysia). I didn't know either of them. They died long before I was born.
She always said that she could accept the death of her brother who died at Dunkirk, presumably killed in battle. However, she remained angry at the "murder" of her brother while a prisoner of war, and often said things like "nobody was brought to justice for it" and that "Japan has never really apologised, and probably never will".
Each time a formal apology was issued, she would say something along the lines of "let's wait and see", and then, later, point out the subsequent actions by the Japanese government which she felt invalidated that apology.
Now, I wouldn't presume to speak for others whose experiences, and so also their opinions, may be different. I agree with Mark C. Wallace's (now deleted) comment:
Some people will never accept the apology. That is their trauma and I won't judge it.
Others might indeed accept an apology, if they can be convinced that it is genuinely sincere. Of course, given the time that has passed without an 'acceptable' apology, convincing them of its sincerity may be the problem.