Entering from Georgia via Goganavan border: 22700 Drams (=48€ by mid august 2010) for the car, which included ecological tax and other stupid concepts, but no brokerage, after I got too stubborn (the guy shouted and blamed my poor Russian when asked for the details, so I asked for receipt, stamps everywhere, signatures, names, talked to the chief, etc; took 3 hours the whole process).
If I tried again, I would take the Bagratashen border, which may have more traffic. We did not cross a single vehicle for 45 min going to Goganavan, so the guys in the border seemed just too pissed to be there for nothing.
21 day visa on arrival with no problem (issued by soldiers, nicer) for 3000AMD for Spaniards.
Leaving to Iran: 6600AMD for the car (again). Bring maaaany photocopies of everything, they'll charge you a lot to make them if you have one missing.
We had a pretty small car, but I don't think it makes any difference the engine size for the pollution tax.
No experience with Nagorno Karabach.