Socim,
Some thoughts.
First, with respect to an accrediting body (AB). If you are in the US, you should NOT sign with any of the six recognized ABs until you get quotes from all six, and that means talk to them, ask technical question, present typical technical issues you encounter to them. Talk to the highest level of management you can. Then and ONLY then should you decide on your AB.
BTW, go though the listings and select a reasonable sample of the AB's current accreditations, call them and ask about the service they get, because that is what you will get.
Now, you need to have certain things nailed down no matter which you select.
Procedures must be validated. Military procedures (older are available through GIDEP) are considered validated.
People must be trained and that must be documented.
Uncertatinties for all types of calibrations must be documented, and for testing you should do the same.
PT/ILC needs to be complete if available.
These are the most basic things to consider. During your discussions with ABs then comfort - though nontangible - may or may not be a consideration.
Hope this helps.