It does sounds as though the fixtures have been wired in series somehow, in which case if you remove all the bulbs from one, the other should stay dark as well.
Assuming that both lights are switched together on 3-ways top and bottom of the stairs, do they react the same way when the switches are turned on the "other" way? (e.g. if both up=on, do the lights still act like this when both switches are down?).
