Having run a few tests I've concluded that the AP victory can be achieved far too easily in
some situations.
As with a UN victory, having a larger map/more civs in the game in makes it much more difficult; it's harder to control the spread of religion, and to gain open borders with everyone for missionary access.
But with a standard 7-civ map it's not at all difficult, so long as the following conditions can be met:
1) You build the AP yourself.
2) You manage to prevent the excessive spread of the AP religion beyond your borders. This makes the later religions the best bets for the palace faith - they don't have as much time to spread before election time. It also means that aggressively spreading an early religion or two is most helpful.
3) You are able to achieve open borders with every civ that the AP religion does not spread to naturally. This could be a real problem if someone like Toku is on the map. Otherwise, it's just a case of making the right diplomatic choices and getting missionaries to their target cities asap (this is one situation where 'no-state religion' and Organised Religion can actually work well together

).
4) You grow your own cities as large as possible (and, if necessary, disrupt the growth of the AI's voting cities with your spies and/or troops).
Even in cases where there's a civ who won't open borders, death or vassalage will end their resistance (or, perhaps, conquer one city, convert it, then trade it back for peace).
The main drawbacks to this approach are that it requires a pretty dedicated effort which could fall flat (especially if Toku forges a powerful empire of heresy on the other side of the world), and that you may risk being DoW'd because your diplomacy is focused on the win, rather than self-preservation.
On small or tiny maps (with the default # of civs) the cheesy AP victory is stupidly easy. Pangea maps or isolated starts should also make it much easier. Oh, and btw, you can't win this way on duel maps unless you create a colony (there must be at least 3 civs present before you can build the AP).
ps. If Sis did want to try out the cheesy victory in this game (I'd rather he didn't), he's got the perfect opportunity. Confucianism would be the best choice for the palace imo.