Shims

Does it sound right that I would have to have shims replaced on all four of my brakes at 51,000 on a RAV4?

Based on what? What was it doing? Had the brake pads been replaced?