If you don't mind renting a car and driving (or if you drive yourself), you can probably get some deals just over the state line in Southaven, MS. It's about a 5-10 minute drive to the airport depending on traffic. There's a Drury, Sleep Inn, Hampton Inn, Days Inn, Residence Inn, Marriot Courtyard, etc all within a mile of each other.