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.