Having searched a couple of times for this information and not finding it (though do correct me if I'm wrong), I thought I might as well post the details here.
Finding the Mongolian Embassy in Almaty is not easy as it's in a residential area and even taxi drivers can't find the address, thanks to Rene via David Berghof for the directions and here is my version of them.
The top bit is...I'm guessing GPS stuff (welcome to the 21st century as my bro would say)
N 43 11 748
E 76 52 022
Start from the Mega Centre Alma-Ata (big shopping centre in the south west of the city).
Ride SOUTH (uphill) past Mega shopping centre to the next lights -
Al Farabi Street, at the lights, turn RIGHT.
Go straight over the roundabout and continue for maybe 1 km.
Turn LEFT just before a petrol station.
500 metres along this road, there is a blue pedistrian crossing signpost. Turn LEFT there through an archway into a housing estate. Go ahead 100 metres it's the first house on the left around the corner.
9.30-12.30 and 2-5.00pm.
But closed on Wednesdays.
Easy application form, cost $58 (British passport- different prices for different nationalities I think).
One photo required and the visa can be picked up 24 hours later.
Nice and easy, I just wish the rest of the visas had been like this
Also Kazakh Registration, which has to be done within five days of crossing into the country, or not needed if staying less than five days.
to do it in Almaty - you need a signed and stamped declaration from your hotel, the registration costs 750 Tenge ($5) and you have to wait 24 hours.
The police station is only open 10.30-12.30 to receive documentation and then hands out the passports with the registration in them 5.00-6.30pm, and they are very strict about the timing.
I didn't get the details but others had assured me that they had found it to be a quick and easy process in other cities.