My biggest surprise with this is the fact that they are paying taxes (for you) on this. Technically, at least as far as I know, it's an expense, which means that they pay for it with no tax consequences to you. I was relocated some years ago, and they tried to pay me it as a bonus (that is, they took out taxes, etc.). I called them up and explained that it was an *expense* (since in my case they were reimbursing me for the cost).
In that case, I'd be surprised if they could consider it relocation costs, since they're taxing it. Legally, you may be able to get it to be considered a bonux (such as a sign-on bonus). In which case, they can't require you to pay *any* of it back (as it becomes part of your salary).
You definitely want to have an lawyer look at it.
Dan