Yes - all our builds are done from zero state i.e. and empty directory. We even deploy a new JVM each time (as we have to test against 3 different JVMs).
Either make your 3rd party librariers part of an OS snapshot, or make it part of your source repository. The flaw seems like it's in your build as opposed to the build system. I'm all for wiping away intermediate work products, but you don't need to test the ability to download 3rd party librariers each time. You could use the md5 or sha1 files that get published to the standard maven repo. and that would be a miniscule download, and once you have it, you could just compare it to the existing files.