I tried the same as you did, and could not replicate the error. But encountered that Qgis sometimes uses another CRS than that stored in the prj file. So take care which CRS is applied to the loaded layers. I did some grids in both 29873 and user defined (red), and they match perfectly.
Here
http://www.georeference.org/forum/t96710 you find test road.zip data with the same prj file as yours, and that offsets to Google imagery only about 20 metres.
EDIT
There are some differences in the proj strings I and you are using:
my QGIS Master 29873:
+proj=omerc +lat_0=4 +lonc=115 +alpha=53.31582047222222 +k=0.99984 +x_0=590476.87 +y_0=442857.65 +gamma=53.13010236111111 +ellps=evrstSS +towgs84=-533.4,669.2,-52.5,0,0,4.28,9.4 +units=m +no_defs
LUKIP QGIS Lisboa 29873:
+proj=omerc +lat_0=4 +lonc=115 +alpha=53.31582047222222 +k=0.99984 +x_0=590476.87 +y_0=442857.65 +ellps=evrstSS +towgs84=-533.4,669.2,-52.5,0,0,4.28,9.4 +units=m +no_defs
SR 29873:
+proj=omerc +lat_0=4 +lonc=115 +alpha=53.31582047222222 +k=0.99984 +x_0=590476.87 +y_0=442857.65 +ellps=evrstSS +units=m +no_defs
Your proj string misses the gamma value. Thats the crazy thing about omerc: The projection axis is not a meridian (as most other merc projections), but with an angle to it. The coordinates are finally reprojected to have north up again. The SR string is even older, and misses the +towgs84 also.
The grid with my proj string in black and yours in red looks like this:
You have taken the proj string from QGIS Lisboa, probably Windows standalone installer. There is a bug in that installer, which prevents QGIS from synchronizing with the built-in GDAL projection database. Installing in a path without blanks (that is not in C:\Programs (x86)\ solves that issue, or using OSGEO4W installer. Master is only available with the later one.
Earlier versions of GDAL had a different way of handling the omerc projection, which was found to be inaccurate, and replaced with the handling of the gamma value. But now you have a new version of GDAL built inside QGIS, but the old proj string in the not-updated CRS database.
You can modify the CRS database, called srs.db, with spatialite GUI (because its a sqlite database as well), or reinstall QGIS to have correct handling of EPSG:29873.
For the Openlayers plugin, the Project CRS must be in EPSG:3857.
Your other layers can have different Layer CRS, if you have enabled On-the-fly-reprojection.
BTW, current version of QGIS is 2.4, and the openlayers plugin does not support older versions anymore.
Best Answer
I'm afraid you are lost with your Malaysian data with QGIS and any other software depending on GDAL and proj. Here is some reading:
http://osgeo-org.1560.n6.nabble.com/RSO-gamma-and-Hotine-Oblique-Mercator-Variant-A-td3841370.html
http://trac.osgeo.org/proj/ticket/104
http://trac.osgeo.org/gdal/ticket/4910
The difficult thing is the omerc projection, which does not use a simple meridian as origin, but a line with an angle to its prime meridian. There are two different versions on how to rotate the data to the line, and rotate back in the end to have north up. Both are defined in proj by a +no_uoff parameter. Unfortunately, this has been lost somewhere between proj, GDAL, ogr2ogr and QGIS (see the last ticket).
EDIT
Still something is working, but NOT inside QGIS:
I installed the latest dev version of GDAL from gisinternals, and reprojected the shapefile with the following :
I first tried with WGS84, but got the offset you mentioned. EPSG:4245 is an older datum used in Malaysia. This is what i got, against Google Physical background: