The values are in decimal degrees. That makes it harder to identify the actual coordinate reference system, because the values are so close. It's a lot easier to differentiate between a UTM and a MTM zone. If the data was collected recently, they may be in NAD 1983 CSRS.
On a related note, the Define Projection tool and the data's property page in ArcCatalog allow you to assign the current coordinate reference system. They update the metadata, not the actual values of the dataset. The data has to be georeferenced / in that coordinate reference system already. To create a new dataset in another coordinate reference system, you use the Project Tool (but the input data must have its correct coordinate ref system!).
If you are creating Vector data, then it's best to keep the data in a geographic coordinate System with WGS84 as the datum.
With today's technology, there is no specific advantage to keep your vector data in a custom projection. 6 decimal points are enough to have meter level accuracy, and you aren't going to need any more. Projection on demand is fast enough in today's world; And you have the advantage of being compatible with most global sources like Satellite Imagery and GPS devices etc.
You shouldn't use a UTM zone, since India is covered by several zones, and big states like AP & MP themselves are covered by several UTM zones.
If you are dealing with any Governemt body, do note that you need to follow the NNRMS standards given in the NNRMS document. While the document clearly states (page 47 section 66.4) that you should store the data in Geographic Coordinate system, all government organizations that I have worked with, store even the vector data in the national or state projections.
Update
In Feb 2016, these coordinate systems were added to the EPSG Database. For example, look at https://epsg.io/7755
Second Update
This projection is now available both in the ArcGIS platform, as well as QGIS, Gdal and other projects which use the updated PROJ library.
If you are digitizing from SOI TopoSheets, It is even more complicated. Firstly, many experts believe that it is not legal to scan and digitize SOI TopoSheets. Secondly these toposheets are in a poly-conic projection, based on the Everest Spheroid & Modified Everest Datum. The coordinates on these maps are shifted quite a bit when compared to coordinates in the WGS84 datum. Hence you need to take care of this datum transformation.
Best Answer
GeoRepository is a great resource for discovering coordinate systems.
Here is a list of possible Projections, but I would suggest you don't take my word for it, I'm not very familiar with that area.