Well, there are several ways to measure complexity. For sheer number of paper pushers and steps required merely to enter a country, Laos wins hands down with sixteen (16) different people processing your application at the border -- see B747-437B's classic Laos-y Report for the full rundown.

For overall bureaucratic pain, expense and time consumed though, getting any form of longer-term visa for Indonesia is right up there. A simple one-year multiple-entry visa (including the prerequisite single-entry visa, which is necessary even if you're otherwise eligible for visa on arrival) will cost approx. US$300 and require three applications (two by you, one by your sponsor) with letters of recommendation, passport photos, proof of transport yadda yadda and, as of this month, visits to the embassy in person to apply for it all. From what I hear actual residence permits like KITAS are considerably worse...