We used to operate the 777 into Bogota (8400 ft) without a problem. It reduced the MTOW by about 80 tonnes but otherwise performance was pretty respectable. The emergency turn (escape route) was quite entertaining on one engine though.
I've been into La Paz on a 757 belonging to AA and that's about as high as it gets, although I understand they're modified somehow or other.