Rob, are you sure it's 316S31? I've found other 300 series steels that are designated S31, such as 320S31 & 321S31 (which do contain slight amounts of titanium), as well as 347S31, 303S31, & 304S31. They all have other designators as well. The designators I've listed are from the BS970 standard, which is/was used in the UK.
Aalco, out of Surrey, lists some, as does
this page.
Maybe it's just me, but since the CNC shop made the mistake, the least they could do is positively identify which specific alloy was used. Most of the alloys I've found are listed as being used in marine environments, with no mention of aerospace use. Of course, that doesn't mean their claim isn't true, but at this point, I'm not inclined to believe it without a specific alloy designator. After all, if they purchase it for an aerospace part and it's a special grade, they must know what specifc alloy is used.