I fixed it myself.
Well, actually I found a work around.
W3TotalCache isn’t taking “custom folders” for images in account even though there is an option to include custom folders.
When I moved the files into one of the “upload” folders within wp-content, the URL began to work.
Seems like a bug in the plugin.