"yet New York is still withholding income taxes"

That is google. They don't have to withhold that. IF google didn't withhold that state tax -- it would be impossible for NY to figure out how much it is owed. You can ask google to not withhold for NY with a HR meeting.