I tried this when I lost Felicity but it doesn't work. I think you can get them back if you let them move and you let another ~16 villagers move out. Or so I've heard that it's 16 villagers. Once you get more to move out there's a chance you can get her back.
With the same Felicity you lost (as in who remembered you)?
Nope, she's in like the void of my town right now and I still see her in the main street. I tried getting Felicity from some other people's towns but it doesn't work at all. I'm not completely sure but I think there's a queue to your villagers and sometimes if you wi-fi with people they get your old villager? Because I got T-Bone from someones town while I was trying to get Felicity and apparently he moved out months ago so I ended up getting him O_O