No, its left vague
The published campaign setting books have not specified a time period necessary for a petitioner to become a full outsider. As you pointed out, it could take a hundred years or more. However, keep in mind that time doesn't necessarily flows at the same speed on all planes, and there may be planes where millennia may happen during a weekend.
As for your specific examples, we know that new archons are born fairly quick (The Great Beyond, p.37):
All the archons that have ever been began their existences as mortals. After their deaths and subsequent arrival before the judges, souls are asked, “Does our judgment suit you?” Many souls nod in agreement—such is the judges’ ability to read the nature and needs of their charges—but souls destined to become archons pause, look up to the summit of the mountain, and shake their heads. Each judge knows the meaning of that response, even if the soul in question might not. The confused spirit is released from the archons’ queue and allowed to wander invariably toward the mountain’s soaring heights. When the spirit returns, descending from the mysterious summit, it does so no longer as a petitioner, but as an archon.
It is also known that demons have specific rituals that transforms a willing mortal into a full-fledged demon.
One way to learn such a ritual from a demon is to use planar ally or planar binding to conjure the demon in question and offer it a payment in return for the secrets of the transformation ritual—this could even be a four-step process requiring a new conjuration for each step of the ritual. Not every demon knows this information, of course, so researching the name of a specific demon can add an additional level of research required before the process can begin. A character might even receive the methods by which to transform into a demon via a series of dreams or visions (typically granted to him from a demonic patron in reward for service), although this route is best left for NPCs that are strictly under the GM’s control.
Finally, some devils are rumored to be spontaneously created from the soul of particularly evil mortals, or even granted their new form by a powerful Archdevil:
While fiendish lords wield transformation into greater or lesser forms as both prize and punishment, some devils spontaneously rise from particularly evil souls long trapped upon an infernal layer.
So, yes. It's perfectly fine to have a BBEG/patron return as an outsider.
All outsiders lose their memories
I know they don’t really keep any proper memories of their old selves
This wasn't true for Golarion until they released Planar Adventures. We knew that the following planes would wipe a petitioner's memory:
- Abbadon, by crossing the River Styx (and may be found stored in a place called The Whirlpool, guarded by Charon);
- Nirvana, as a side effect of joining the plane, the memories of all mortals are wiped clean by the gods;
- First World has memory-eating fogs, but those can be avoided;
But other than that, there was nothing about losing their memories in the afterlife or by crossing Pharasma's Boneyard. From The Great Beyond (p.6):
In the process of their migration through the Astral, the dross of mortality is shed, leaving behind only their core self, their memories, and the refined character of their prior life.
However, that changed completely with the release of Planar Adventures, which now says:
Once a mortal soul has been judged and sent on to its final reward, it may become an outsider known as a petitioner. The process of becoming a petitioner wipes away personality and memory from the soul, and in time a petitioner could ascend to a higher form of outsider life; gradually merge with the structure of the plane; or be destroyed by peril, misadventure, or predators. When a petitioner dies in this way, its body decays away, its energy recycled back into the quintessence of the plane.