i believe this lock is not the usual apple iCloud lock.
Just phone blocked from use in Malaysia telco. ie, can't call/sms/data only.
I dont think Maxis can totally lock out the phone.

Can still use phone for others, wifi, games, etc.

from what i can see, you only got few options:
1) get original owner to pay the bills and finish the contract (very likely to be impossible)
2) you pay off the contract yourself (stupid move)
3) continue to use as iPod (haha)
4) sell off to another country (looks like the best solution)

pretty sure even changing sim or telco in malaysia will not work.

best bet is try using in overseas.