My reading indicates that "Darth," Maul was never a true lord of the Sith, nor a true apprentice of Sideous.
I claim that Dooku was Sideous's true apprentice before Maul died.
According to Wookiepedia, "He[Dooku] left the Order, becoming one of the Lost Twenty. He then regained his family's wealth and the title of Count of Serenno. Dooku was then approached by the Sith Lord, Darth Sidious, who asked for his help. Craving power, Dooku joined him and was given the Sith name, Darth Tyranus. As Tyranus, Dooku arranged the death of Jedi Master Sifo-Dyas by contacting Lom Pyke of the Pyke Syndicate to shoot him down. Dooku was then given Sifo-Dyas's body. However, Dooku was unaware that the Pykes had captured Valorum's aide, Silman, alive. On one of the moons of Bogden, Dooku then recruited the bounty hunter Jango Fett as the template for the Clone Army Sifo-Dyas ordered from the Kaminoans." from http://starwars.wikia.com/wiki/Dooku
This indicates that Dooku was in the employ of Palpatine while Maul was still alive, though I'm not entirely sure that this is the case. The fact that the clone troops "were completed within a decade—approximately ten years after the Battle of Naboo," implies that Dooku had been approached before Maul's death.
We have further proof that Sideous perverted the Rule of Two in EU canon based on Starkiller, Mara Jade, the other hand of the Emperor, and others. Using an insane murder machine as an assassin is not out of character for him. I will also claim that Sideous did not truly pervert the Rule of Two by claiming to have multiple apprentices as long as he didn't teach them anything appreciable. Not even combined could his later force users face off against him (except possibly Starkiller, but that was not part of his plan).
Based on Maul's journal, and Darth Maul: Shadowhunter, we see a sentient without much training in the force aside from assassination techniques. We know that he spent a great deal of time building a lightsaber, but he laments the lack of time spent in personal training. He is taught more often by droids or told to meditate by himself. This is reminiscent of Starkiller's training at the hands of Vader (who was definitely not a true apprentice) and the techniques are similar to what Mara Jade was taught (also nto a true apprentice).
In order to become a true Sith Lord capable of defeating Sideous and continuing the RoT, Maul would have needed far more control over force techniques rather than just his lightsaber. His stealth and rage however, make him feel better suited to the Assassin or Marauders mentioned in Darth Bane: Path of Destruction, and KoToR II. Finally, Palpatine's political plans were not spur of the moment. He knew that he was going to be a senator, otherwise he would not have spent so long on that persona. A tattooed Zabrak with anger problems with no political training would never have been able to take over any political machinations Palpatine set up.
In summary: Sideous never intended Maul to be a true apprentice and was instead using him as a skillful killer, OR Sideous was perverting the RoT because he didn't want to ever be replaced.