I was able to remedy the issue when I first encountered it by installing an older version of the plugin. I believe its 1.9.2. I only encountered the Malware issue when I updated.
Seems to have been issue free since.
After cleaning up the code, changing all passwords, and getting things back up and running, I wanted to start adding back in the latest versions of all of the plugins I use.
The very first plugin that I added back in was NextGen Gallery. Immediately had Malware warnings again. I deleted the plugin and things went back to normal. No Malware warnings. My only guess is that somehow the plugin has been compromised.
Hopefully someone can shed some light on the issue.