UPDATE:
I downloaded the Better Privacy plugin to get rid of Flash cookies. My process is to clear the cache, delete cookies, delete Flash cookies, close and reopen the browser.
I thought this would work, but I just tried to create a new account on Tumblr. When I tried to log in, I got an "incorrect password" message (even though I'm 100% sure it was the password I set up) I requested a password change email, which I used to set a new password, but I got an "account terminated" message.
All I can think of now is that the paid proxy I'm using has been used before on Tumblr for spam. This isn't really a huge deal; there are plenty of other web 2.0 services that don't care or don't have the methods to detect this. I'm just wondering how I could get around it, because Tumblr and Wordpress (the ones who seem to terminate accounts immediately) are very high PR.