It should be no issue for your payroll company. This has happened to our company. The important thing is to pay her. By law you must meet payroll and you must pay your employees. Any violation can trigger an audit and you don’t want that.
As long as the time period she was working was covered by her visa, you’re in the clear. If you are saying that she overstayed her visa, you still have to pay her, but you need to consult your lawyer, because you were in violation of the law, if she worked anytime passed her stay.