Last I heard, Mongolian Embassy in Beijing is issuing one-day visas if you are willing to pay more, RMB 495 I think. Normal processing is 5 days and closer to RMB 300.
Hours to make application: Monday, Wednesday, Friday 08:30-11:30 and Tuesday, Thursday 14:00-16:00
Hours to pick up visa: Monday thru Friday 16:00-17:00.
(Note that sometimes the Mongolian Embassy changes it's visa application days/hours around a bit, so it is best to check again just before heading for Beijing.) In the summer there are often long queues to make visa application, but in March, probably not too many people. I'd still plan to show up at opening time on whatever day you choose.
You do realize that in March, there is so little tourism in Mongolia that many things like tourist ger camps, etc. will not be open? I'm not sure about National Parks. You may want to check your itinerary in Mongolia with a local agent, to see if you might be making a long trip for nothing. That would be a shame.
Also if you are coming through China, you will also need to get Chinese visas. If you are returning home via China overland OR by a plane flight with > 24 hour stopover, you will need a double-entry visa. Another alternative that avoids China is to fly to Ulan Bator directly via Seoul, South Korea. I'm not sure what the visa application hours/fees are at the Mongolian Embassy in Seoul.