[lootabooga]

You could use a WP plugin that stores them on Amazon S3. It's not free, but it's like < $1 month for normal blog needs.

[picardo]

The only plugin available explicitly states (on the Settings page, after you install and avtiavate it) that it doesn't upload directly to S3. It has to upload to your server first.

edit: actually, I think the upload to S3 button is different from upload media button. That's why I didn't see it.