AA has been great for award availability. My only problem with them is being able to find award availability in premium classes going transcontinental very far in advance. However, when my honeymoon flights got all messed up with a schedule change by a partner airline (TN), AA was nice enough to get revenue management to release the premium seats for us. They didn't have to do that, but they did it anyway! Very nice!

CO? Why even bother!

DL? I've had friends who have had a pretty decent success rate on DL partners for international flights.