This week Bulgaria Air began flying from Sofia to Skopje - the first air link between Bulgaria and the Republic of Macedonia. Fares are advertised at 49 euro one way. I tried a few test bookings on the Bulgaria Air site and found that flights are indeed generally available at this price - but taxes, charges, and services fees bring the price up to 90 euro.
For comparison, buses run about 6 times daily on this route, take about 5 hours, and cost less than 15 euro one way - with the bonus that they take you from city centre to city centre. Taking the bus also means you avoid having to deal with predatory taxi drivers at uncivilised hours of the night: the thrice-weekly flights leave Skopje at 06:05 and Sofia at 23:15. But given the relatively poor choice of direct flights from Skopje itself, the new route may prove useful to some travellers trying to reach Skopje from further afield.
Air Bulgaria also plans to start flying to Belgrade in 2008.