What is the most novel and realistic (believable) way for a relatively average character, with a military background to "disappear" and go underground ("off the grid"), eliminating as many traces of himself as possible (in a modern setting).
There are several assumptions that will have to be made by the character in order to successfully exist "off the grid".
First and foremost, will the character ever want to reemerge? Their identity and resources will then have to be securely cached somehow, and a backstory of sorts will also have to be created to cover both the disappearance and the eventual re-emergence. The IRS or whatever tax agency of the nation that person comes from will be most interested in their whereabouts and sources of income during their disappearance, for example. Being ex military, various intelligence agencies might also be concerned as to where this individual has gone and what they might be doing while underground. Serving as a military contractor (officially or unofficially) may or may not be looked upon with approval, especially if this person had sensitive skills or might be considered to be working for the "wrong" set of people. Even legally, vanishing without a trace will result in a missing persons report and potentially being declared dead after seven years (depending on where this happens) and the State disposing of the assets according to the local laws.
If this is not the case, and the person wishes to effectively vanish forever, then they need to be constantly on the move, have a broad skill set to allow them to find employment wherever they go and/or live off the land, and be prepared to use only cash for any transaction.
You can still conceivably live a nomadic lifestyle in many places around the world, working off the books and paying cash for motel rooms and food at diners or their equivalents. IF you have the skills, linguistic ability and attitude, you might really go off the grid and join a nomadic society in a very far off place like Mongolia (where you will be off the grid almost by definition). Even working underground as a general labourer in parts of the United States isn't going to be too hard (there are anywhere from 11 to 30 million illegal immigrants doing just that right now), so long as you are careful not to attract any attention to yourself.
There are vast tracts of wilderness in North America and other parts of the world, which will allow you to really "live off the land" assuming you have the skills and inclinations, but you will be limited to whatever tools and equipment you brought in initially, and eventually may "devolve" into a neolithic hunter gatherer lifestyle since you will not be interfacing with society for tools and equipment.
Alternatively, you could live underground in many third world nations which have lax law enforcement and where many officials can be "persuaded" to look the other way. You will most likely be working on the fringes of the economy and interfacing with the criminal elements (I would strongly suggest that anyone really considering something like this to think again, these are not good people to be associated with), even if you are doing nothing more than providing a "safe house" or allowing questionable people to come by and drop off things in your garden shed from time to time.
So staying on the move, working as an "undocumented worker" and using only cash transactions will provide the 90% solution. There is always a chance of running into someone who knows you, and of course there are unexpected ways of being "revealed" to the authorities (perhaps you are on a bus which is involved in an accident).