Based on the OP's description, it's difficult to determine the current state of the system with respect to a compromised Magento. Unfortunately, as I discuss below, installing the fixes will not resolve your problem if you are already compromised. They only stop future attacks, They DO NOT DO ANYTHING TO FIX A SYSTEM THAT IS ALREADY COMPROMISED.
We've documented our research to provide a list of known attack signatures so that you can check your systems for evidence of them and respond accordingly. Keep in mind we've never seen two compromises that are exactly the same, so there's a chance your particular system might be slightly different - if you discover anything on your system that we don't already have documented, please share that with us so we can update the attack signature guide or just fork, update and submit a pull request.
We're working on a toolkit to automate the remediation of these item but it may be a week or two until it's ready for distribution. In the meantime, we're sharing the knowledge we've acquired working through these compromises with everyone in the community in an effort to make sure everyone is as safe as can be expected.
I'm including a 3-Step Security Analysis & Response Process below that we've worked over and over again to get consistent results. The key assumption you're going to have to make is that you can't know what has or hasn't been compromised until you diff the files in your system against the default source code provided by Magento or a copy you have made in your (Git / Mercurial / SVN) repository. YOU SHOULD ASSUME that your database and logins have been compromised and go change them all.
CRITICAL NOTE: Installing the patches from Magento WILL NOT help you if you have already been compromised. At best, it will stop ADDITIONAL compromises of the known types, but if you are already compromised then you'll have to BOTH install the patches and remediate your system as we highlight below.
Phase 1: Identify the scope of your compromise. Each and every one of the items I list below are signatures we've discovered on compromised Magento sites specifically relating to the SUPEE-5344 and SUPEE-5994 vulnerability announcements. After you've installed the most recent patches (and any others you may need to install from Magento), you need to go through each one and check to see if you find any evidence of the signature on your system. Many of them are enough by themselves to allow an attacker to re-enter your system after you patch it, so you'll have to be diligent and make sure you don't skip anything or fail to remediate it.
You can also use the online scanner from Magento, but by and large these only will tell you if you've installed the patches and prevented future compromises. If you've already been compromised, these won't scan for other back doors or attacks that may have been installed when you were first attacked. at least none of the ones we tested found the signatures we discovered. Defense in depth is the way to go, which means multiple scans and reviews from multiple tools and perspectives if you want to be confident in the results.
Phase 2: Delete what you must, and replace what you can : use the original files from your repository or the Magento source files. If you're not running one of the latest versions, you can still use the Magento download page to grab older version sources from their site.
Phase 3: RESET Credentials: Inventory every use of a login name and password remotely related to your deployment and reset them all, including
- Merchant Account Logins and API Keys
- Magento Admin Logins & Passwords
- Email account credentials
- LDAP / AD / Primary Authentication System
- You can be reasonably sure that the preceding steps will help you purge infected fies but you can not know if passwords have been sniffed or key logged or the victim of some other attack, so resetting all related credentials is the safest option if you are going to attempt to remediate a compromised system.
The guide is too long to post in this response but the signature list can be downloaded immediately at our Magento Security Toolkit GitHub repository.