I think catapults would probably work fine. I've never seen a lump of flying rock be beaten by an albatross.
Is it because
nobody has ever seen a lump of flying rock hit an albatross?
Alright, this is just theorycrafting for a while. What we know: hitting a target on a single z-level is hard enough with siege engines, let alone on a 3D level. This is compounded by siege engines only firing targets on their own z-level. If we're going to use the literal approach (ie Skullsploder's suggestion) without cheap tricks, war animals will have to be used to herd the birds into a smaller 'slice' of the z-axis.
Then comes the problem of wasting all the ballista bolts. A possible arrangement would be to have the ballista bolts hit a wall on the other side of the embark, and thus fall downwards. To avoid hauling those bolts all the way back to the original battery, we can have another series of ballistas (on a different z-level) there too, which essentially means that the ammo will go through a continuous 'cycle'.
Side view
..B----------------------->.O
..B----------------------->.O
..B----------------------->.O
O.<-----------------------B..
O.<-----------------------B..
O.<-----------------------B..
B ballista
O walls
-> direction of ballista bolt fire
Then again, the scale of this device is compounded by each B being a
row of ballista batteries covering the horizontal axis, instead of just a single ballista.