It sounds like you are on the right track. Your site may already be cleaner than you think. The seemingly random occurrences of this hack may be simply due to caching on either the browser or the web-server side. If you have any caching plugins you should deactivate them.
Also, check Google Webmaster Tools to see if it shows any infected URLs in the health section. You can also fetch a page from your site as the Google Bot to see if it still contains any malicious code.