Okay, I finally got it working... sorta.
What I ended up doing was giving up on keeping it dynamic and instead made the goal of always having the form load up when the page is loaded no matter what. That means the vote form itself gets cached and then people can use it to vote and/or view the results via AJAX (which are cache independent).
To get the form to display even if a person had voted before (previously if a person had voted, it'd display the results off the bat), I did a little hack in my theme.
That alone works, but I went a step further. By default, Democracy sets a cookie when you vote. This is a problem because in order to show you the right page, WP-Cache takes cookies into account. For example, if you (an average user) view my site, you'll get a different page (and cache file) than me because I have a cookie that says I'm logged in.
Now of course many, many people will have a cookie that says they have voted in poll A, but the problem occurs when we move on to new polls. There would need to be a cache for people who have a cookie for poll A, a cache for people who have a cookie for B, and a cache for people who voted for both. And the problem gets worse with the more polls that are made.
So, I removed the line that sets the cookie and left duplicate vote protection to just IP logging alone. Of course this can lead to problems for those sharing an IP (can't vote) or those with a dynamic IP (can vote more than once), but I think the problems should be minimal.
Anyway, just thought I'd share what I ended up doing and you can see it in action at FinalGear.com.