Yes, all the rest services have to be projected in the same spatial projection. If you choose to mash-up ESRI, Google, Bing,... services then your rest services must also be in WKID 102100/3857 to allow them all to show up on a common map.
However there are multiple mehtods to get your data into a common projection. The most extreme way is to reproject your source data into that projection, this makes data display most efficient but you will lose the accuracy of your local projection. The least extreme is to force arcgis server to preproject your data on-the-fly to the desired projection. Reprojecting-on-the-fly is very processor intensive so the service draw time will suffer. For static data, reprojecting-on-the-fly with caching will negates the issue completely. Another option is to reproject your data into another GDB (FGDB on the same server as AGS is most efficient but cannot be web-edited through a Feature service). In my opinion, the best anwser is a combination of methods based on the specific use of that data: reproject some data into a FGDB, cache other data, and reproject-on-the-fly edit data.
