Illustrator: yes, although if the documents use features specific to newer versions, parts may be rasterized or give unexpected results. Same applies to Photoshop if the documents are saved as .psd. TIFF won't have any issues. Indesign isn't as seamless. http://helpx.adobe.com/indesign/kb/save-indesign-files-previous-versions.html
Personally, if a vendor isn't keeping up with my workflow, I'd be looking for a new service bureau.
You shouldn't have any issues with .PSD files if you use the option to "Maximize PDS and PSB file compatibility", either setting "always" or "ask". If the latter, be careful to click OK when asked if you are saving a file that will be sent to a service bureau.
If the service bureau will not need to edit the files then saving as TIFF without layers is an excellent option. The files will be more compact as some of PS's special embedded data used for its proprietary features will be omitted. Also, you can reopen these TIFFs in PS and see exactly how any of PS's live features have been rendered.