I'm going to start by saying that the outcome for these veterans.... Seeing as they've given their lives for their country, they should be given whatever services they need to get back, to have fulfilled lives after service.
Let me be completely honest: this seems much more complicated than necessary.
Sharing information between the two departments seems to be the solution, but that is not what is happening. I have trouble understanding why, since this is the only way to make sure that every veteran receives the services they need.
One of the biggest problems is probably related to the culture in the two departments. I do not know exactly what the problem is, but it is certainly related to the culture. Typically, if you want to change the culture in an institution or department, it has to be from the top down.
I don't know what the structure is within the department, but can we have a bit more information as to where you think the problem lies?