Any big outstanding loan ? Or you're a guarantor of some big loans ? Have you paid a visit to BNM to check your CCRIS ? A paycheck above 70k per annum is way above the minimum criteria to qualify for a credit card. Unless there is something seriously wrong or else i can't think of any reason why banks kept rejecting your application.

Any charges to stolen MBB/CIMB CCs?

Even with police report? Nice, adds to the losts 

what are you using when u apply CC?

pay slip?

UOB will waive the replacement fee if you submit your police report. However, you need to come in person to the card centre in Jalan Raja Laut. (Not sure what will be the case for outstation cases) The card replacement fee is RM 50 if you opt to pay for it.

I would suggest getting a FD pledged card with PBB or such to establish your track records for the first few years. This would probably be easier and based on your income, should not be a problem. Otherwise I am afraid your chances are pretty slim based on my experience in the banking sector. However, that's just my 2 cents worth. Best of luck anyway.