Apparently you get a different answer from each person that you ask including the people who work at the ticket counter.
Well, regular buses to Ajmer (and to Pushkar) are private buses so you pay for the ticket on the bus and ask for any info there as well. I still got a wrong answer though.
I did get a correct answer by asking at a guesthouse where I stayed. Buses run 24/7 which was a great thing to hear and it was completely correct. Buses head to Ajmer every half an hour from Marwar bus station (a bus stop to the North of the lake).
I took a bus at 6:30 AM so I can confirm it runs as stated. I've also seen buses going for Ajmer at 2:00 and 3:30 AM so that means that there really are buses all night long.
One thing I noticed as well is that there's a bunch of trucks, "vans", cars and other vehicles whose drivers ask you whether you want a transfer to Ajmer (they offered for 150 rupees, but I guess you could get it for 50). A bus ride is 10-12 rupees one way depending on the conductor.