This might belong in off topic, so if you don't get many replies, try there...
I am sure you will get a ton of thoughts on this issue. Here are mine.
As someone who has worked in IT for over 10 years, and now I do hiring in IT for the company I work for, there are 4 things I look for in a candidate.
1. Education - Nothing replaces a college degree. I have a 4 year degree in CIS and it continues to help me.
2. Certifications - Having these does help the cause if they are up to date. Obviously, a MCP in Windows NT 4.0 is not worth as much as one in Windows 2000 or 2003 Server.
3. Experience - Self-explanatory
4. Knowledge - What software, hardware, topologies, technologies, etc. do you know.
A balance on all 4 will get you the job you are looking for. Certifications without the rest won't help you in the long run. I remember back in the dot com boom when certifications were seen as a bypass from college. Hundreds of kids got certifications and got jobs. However, the problem was these kids didn't have the experience or the education to really make a big impact or stay in the job market. Now, just getting that MCSE isn't going to help you much if you don't have the experience, knowledge, or education to back it up.
I don't know your education background, but you should have some good experience while in the military. Now you will need to continue to get good experience in the computer sector. Working as a PC/Network tech is a good start. My current job expanded into a directors position from a PC/Network tech in fact. Would a MCSE help you? I would say a college degree in CIS AND a MCSE would help you the best. Maybe you can go back to college and get both while getting college credit at the same time?
Good luck!