On the contrary, Randy Weston is very well recorded. I don't know the deal on yourmusic.com—unfamiliar with the site—but he's been making records since the '50s, and I think he was even nominated for a Grammy in the '90s. One problem with these downloading sites is that they tend to only have music that was (or has become) semi-popular—basically, stuff they think they can make money off of. Unfortunately, that leaves out a lot of great music; with just a few exceptions the absolute best music has often happened outside the mainstream. Even many of Miles Davis' records didn't sell well when they were made, but since he was on a major label his records always have a chance at a second hearing.
Anyway, if you're looking for records, you might try With These Hands or maybe Solo, Duo and Trio.
For Jaki Byard, I'd say try to find a trio record called Hi-Fly. Interestingly enough, the title track just happens to be one of Weston's most famous tunes; many people have recorded it. (Weston's other sorta well-known tune is "Little Niles".) The record also has an amazing version of Monk's "'Round Midnight."