If you know the name of the app why didn't you just uninstall it? If you can't uninstall an app the first thing to check is that it's not been set as a device administrator (and to unset it if it has). And the app name is still very generic, so you'd need to provide a Play Store link or developer name to identify it. However, what you are describing does not sound like the behaviour of an SMS backup app, nor any sort of app you can install from the Play Store.
More seriously, if you have factory reset and you still have problems there are 3 possibilities:
1) You have restored from a backup after resetting, including restoring the problem app.
2) Someone has installed something much nastier, which has infected the system partition (which is unaffected by a reset - you need to completely reflash the phone software to get rid of that). You won't find stuff that does this in the Play Store.
3) Someone has access to your Google account, which allows them to put stuff back on your phone after a reset.
At the very least you should clear the device of suspect apps (factory reset if necessary), change your Google account password and enable two-factor authentication (to prevent someone accessing it from another device). In that order: do not change the password and then reset the device, as you are likely to trigger anti-theft measures and be locked out of the phone for a couple of days, and in any case if you think there is spyware on the phone there is no point changing the password until you have removed it.
And if you think your girlfriend is responsible you must also not give her unsupervised access to your phone (including changing your unlock pattern/PIN/whatever to lock her out if she gets hold of it without your knowledge).