I haven't tried, but in principle you should be able to remove mahjong from the command line.
Open an xterm, sudo gainroot (or whatever you do to get root on your version), then
dpkg --list|grep mahj
After that,
dpkg --purge <list the packages that was output of the above>
That should work, unless there are some crazy dependencies somewhere in the system (on which you would blame Nokia).
On my system those games are not listed in the application manager, so it looks like the above is the only way. Unless enabling red pill mode will make them visible in the application manager.
I too would like to uninstall some of the built-in apps, but I think the problem is that then osso-software-version-rx*4 will be removed too, meaning the Seamless Software Updates won't work.
When in red pill mode and trying to uninstall some junk that comes with the latest version of Diablo, every single file seems to have a dependency on OS2008 Feature upgrade (unlocked).
