Zonder koeling kun je zo'n 3 watt dissiperen in de 7812. Bij een aangevoerde spanning van 36 volt kun je dan maximaal 125mA afnemen. Wellicht evengoed voldoende voor de Arduino , maar toch... overigens is de maximale aangevoerde spanning volgens de data sheet 35 Volt. Het zal wel gaan met 36 volt maar het werkt aan de grenzen.
Ik zou de 12 volt voeding er ook gewoon bij laten.