I've seen Alpine Choughs at the top of the Aiguille Midi in France (3,800m). They nest up there safe from predators, fly down into the valleys to feed in the morning and then ride the thermals back up to their nests. They are also a very attractive bird with a striking metallic clatter of a voice.
However that's far below the record. If you do a Google for 'bird flight records' you find the following:
http://www.earthlife.net/birds/records.html
"Highest recorded flight = Ruppell's Griffon Vulture
Gyps ruepellii recorded flying at 11,277m/37,000ft, at this height human beings would die from lack of air."
Now I've no idea if this is a good source or not, but I've heard that some species migrate over the Himalayas, and also that migrating swans have been seen at very high altitudes to the NW of the UK.
The new trend to follow bird migration by fitting some birds with minature GPS receivers might shed more light over the coming years.