I don't have any canon backup, but one obvious thing leaps to mind; it's the veil between life and death, and a living being passing thru it seems to never come back... but we don't really know what happens to them.
Perhaps they are now in a Dante-esque 'Living being in the realm of death' state, or something similarly odd. No one has gone thru and come back to tell the tale, so what it does is really unknown. ("The undiscovered Country, from whose bourn No Traveller returns" to quote the bard.)
Basically, we really have no way to know WHAT it would do to a Horcrux. Do you really want to take a chance on tossing an item which, so long as it is intact, keeps an evil wizard alive, into a realm where you can't get it back if it's not destroyed?
It's in the Dept. of Mysteries, so they are apparently researching it.. But without having much better data, I wouldn't have tried destroying a Horcrux with it.
Also, Dumbledore didn't have all of them to toss thru; that was Harry's quest. He didn't try it with one that he reclaimed (the ring), because A.) He did something stupid with it first, and B.) He knew of another way to destroy it with what he had on-hand. Then there was the book.. but Harry took care of that... Overall HOW to destroy them doesn't seem to have been such an issue, as acquiring them.