X30,
I don't know if it is illegal or not (it sure does sound illegal). Is this a pay cheque that is handwritten on the company's check book or is this processed through payroll or by another payroll processing company?
And, do you have a valid H-1B visa (I assume you do)? Does the pay cheque match what is on your LCA and H-1B1 petition? What is the reason given by your company for refusing a paystub?
Finally, what is the name of your company? I hope that you are not in a rock and a hard place that will prevent you from sharing this information.
-Palaniappan Rajaram