If the the current coordinate system of the data is correct, you can now use the Project Tool to project/transform the features in the existing shapefile to a new one that uses the RSO coordinate system.
You have to have v9.0 or 9.1. RSO was not supported at version 8.3 or earlier.
If the other data has RSO as the defined coordinate system, ArcMap should already be able to overlay the data on-the-fly.
You will need to set a geographic (datum) transformation from WGS84 to Kertau or Timbalai. There are several transformations that are good for different areas, so check in the desktop help, table of contents, map projections. The first topic has link to PDF files. One of them has lists of the supported geographic transformations and their areas of use.
ESRI Product Specialist