Just a heads up -
I went to a travel agency this morning to get a Lao visa in Phnom Penh. They said it would cost 37$ USD and it would take one day. After reading on the net I figured the agency is making about $7 on the job so I decided to go to the Laos Emabassy in Phnom Penh and get on on my own. I was speechless to find out at the embassy, after filling in all my forms and having the 3 pictures, that they were charging 47$ USD for a 48 hour turn around and 57$USD for a 12 hour turn around. Those were the only two options.
So, either get your visa at a travel agent or at a border or at the airport, but not in Phenom Penh. I'm sure Bangkok is better.
This is as of today, Nov 6 2007.