Is it normal for US PhD programs to require students to pay tuition for extra credits beyond 9 credits/semester? Last semester I chose 12 credits, but the department said it can only pay for 9 credits, i.e. I have to pay for the extra 3 credits by myself. 

No one ever told me about such rules before. I thought the tuition fees for phd students are just a fiction/imaginary/symbolic number. Is there anyone who have heard things like this?

I think it is ridiculous to ask a phd student to pay. Because phd is kind of a job, I have heard employees getting very low salary, but never heard of an employee PAYING her company.
Yes, this doesn't sound too unusual.  It's certainly pretty common to have restrictions on the number of courses that grad students can take.  Some schools might make you pay for any extras, and at others they might not let you do it at all.

This may be a result of the university's internal budgeting: tuition is charged by the credit, and the student's tuition waiver is limited to a certain dollar amount.  This helps the institution keep some control over the "cost" of supporting a graduate student.  The tuition fees may be fictitious to the student (up to a point), but I assure you that to the departments within the university whose budgets are affected, those dollar amounts are very real.

I'd also interpret this as a warning that you are taking more classes than the standard load, which may not be a good idea.  It's very common for PhD students to take on more work than they end up being able to handle, and the results are often not pretty; sometimes this sort of thing starts a spiral that ends with the student dropping out of the program.  So I'd suggest caution before trying to push through the restriction: it might be a blessing in disguise.

Note that PhD students generally exist in sort of a gray area between "student" and "employee", and so your analogy of an employee paying her company is not really apt. Some academic cultures put them closer to one side than the other, but as you're finding, it's often necessary to balance aspects of both.