Bits and pieces of good information. For a perspective, there are two issues, the first is seminal, the second of less importance.
About 40 years ago, DoD agreed to withhold State taxes from military pay. This was a very big deal in military circles, as at that time very few military folks bothered to pay state taxes. The agreement was that the services would withhold taxes based on a members “of record” state of residency. Without going into a bunch of legal mumbo jumbo, once the state has your money, you are going to have a hard time convincing them to give it back to you. So, the objective is to not have the Navy (or others) withhold state taxes and give your money to the states in the first place. The only way to prevent withholding of taxes for a specific state to is to go to PSD and convince them you are now a resident of ____ state, and make an "of record" entry into your service jacket. Best if it is a state that does not have income taxes. Various PSD’s (and folk within PSD) have various “proof” requirements. So the arguments of a “drivers license”, “own property”, “voter registration”, et al., are mute. You must convince the PSD folks, so you must find out their requirements. They vary..
The second issue is the states and the states’ interests. They want your money, however, they are prevented by various statutes from aggressive action. To be sure, they are not happy about the situation but there is little they can do about it. Disclaimer. I have no legal stature, so any legal advice I would give is worthless. But I would guess that if there were something the states could do about it, they would have done so long ago.
About 2 years ago, California made an attempt to recover. I am not sure how successful they were in the process. Apparently, they mined all available databases and anyone they found living in California that did not file an income tax return, they sent to them a nice letter telling them to pay or show cause or go to jail. Many military folk received this letter.
