Why were birds of paradise formerly thought to be without feet?

Because they were and are worn as ornaments in

India, on account of their beautiful plumage; and when sold for this purpose, the Passous still cut off the feet. - Blumenbach.