Benja, I would recommend sending the old tenant a certified letter or something saying that they owe you money--that way they can't claim that they "didn't know" or whatever. Plus, filing in small claims court is very easy and will probably cost you ~$100 (which you'll get back if you win).
Many years ago, I was moving out of state for a few months but wanted to keep my place, so I paid my landlady two months rent in advance. Four days before I left she told me that she was getting divorced and was selling the house (both true) and I had to be out in 96 hours. She was a nice lady and we felt bad for her, so Mrs. WonderMeal and I complied. She wrote me a check for the $3000 she owed me (two months advance rent + security deposit) and we went our separate ways
Two weeks later, I realized she had canceled the check, pocketed my $3000, and had dropped off the face of the earth. She had a very common name, so it was hard to track her down. About six months later, after about a million unreturned phone calls, I had my out-of-state friend call her from a strange number. "Jan from the cable company" told my landlady that she had a $17 refund from her service at her old address but that the check was returned. The landlady promptly gave her new address to "Jan," and three days later she received a certified letter that included her court date in small claims court.
Rather than go to small claims court and potentially have to pay 3x the amount of my security deposit + the two months rent + any of my attorney fees if I won (the law of the state I was in), we settled for $4k. It was a hassle to do all of that stuff, but it sure felt good to cash that $4000 check.
