Let's clear up the first question: "the most banal" is right, and good sounding.
Now then, in order for something to be "superlativest", it needs to be "comparativer" than everything else. (I use these ridiculous terms in jest, of course).
In other words, we need "banaler" to exist if we are going to have "banalest".
In forming comparatives and superlatives, we should proceed with caution, because many words formed by the "-er" and "-est" pattern are silly. This is especially true with words of foreign origin.
Slippery slope argument: how far are you willing to go? Would you stick "-er" and "-est" on, say, touché?
Your point is touché, but Bob's is touchéer and mine is the touchéest of them all!
And if just one of the two sounds silly (either the comparative or the superlative), the other one is out of the question also. Thus, even if "banalest" seems passable, we have to condemn it for its inseparable pairing with "banaler".
It is actually of little surprise that among the 503 unenlightened uses of a silly word, you also found quite a lot of bad grammar. Someone who thinks "banalest" is a fine word likely has no problem sticking "most" in front of a superlative.
Okay, so now to confront the question I've been avoiding: why are "banaler" and "banalest" silly sounding? Here is a hypothesis that is hopefully plausible: it is because they are treated by the listener as "-al" adjectives, which generally don't accept this formation. Such adjectives generally do not denote comparable quantities and so the comparative and superlative do not makes sense and are not heard:
maternal, maternaler*, maternalest*
abdominal, abdominaler*, abdominalest*
diurnal, diurnaler*, diurnalest*
original, originaler*, originalest*
infernal, infernaler*, infernalest*
internal, internaler*, internalest*
national, nationaler*, nationalest*
adrenal, adrenaler*, adrenalest*
The question remains is whether these words should be even be used with "more" and "most". "The most abdominal muscle" sounds grammatically fine, but is nonsense. They have to be considered on a case-by-case basis. Something being more banal than another seems like a valid concept.