En resumen, el estudio citado en la pregunta aceptada indica tres teorías acerca del origen de requete.
En los tres casos se habla de una metátesis, es decir, hay un cambio en la posición de los sonidos de una palabra.
1. Se habría originado a partir de la interjección reteque, que se usa estribillos de un estilo africano llamado zarambeque, muy popular en España desde el siglo XVII. Por ejemplo en Volatines y mojiganga:
Pus qui vengo á rienda suelta
por sólo curar su vuelta
con vueltas del zarambeque,
teque, reteque, teque, reteque.
En un entremés de Antonio de Solis llamado El niño caballero, en el que se baila y canta zambeques, aparecen dos personajes llamados Teque y Reteque, que son gigantes, y de ahí proviene una expresión aparentemente conocida en España: A teque reteque, que significa "repleto". De este gigante Reteque vendrían los prefijos rete- y requete-.
2. A partir de la antigua forma quetarré, siguiendo aproximadamente la siguiente vía:
¡qué tan reviejo! > quetarré viejo > requete viejo
3. A partir del prefijo tatara (el de tatarabuelo), intensificado con un re-, de la siguiente forma:
tatara feo > retata feo > recata feo > requete feo
Como sea, es de origen andaluz y, junto a rete, es el prefijo de aparición más reciente en la lengua española.