I've used Sallie Mae twice. I've never had a problem with Sallie Mae. As with Sarah, I've never been sent payment books, but I just signed up for online billpay. It makes life a lot easier. My first loan was for 21k and my payments were roughly $250 per month, the loan I just got was for 12k, and my payments are $150 per month. All my disbursements have been on time. You also have the option of paying interest only payments while you're in school.
My roommate while I was in Florida had a loan through Key. I don't know the details, but I know he never had a problem.
**flyitup, sorry to hear that you had a problem with Sallie Mae. Any idea on when you're gonna get to start flying again? We need to go up sometime!