My biggest surprise with this is the fact that they are paying taxes (for you) on this.
No they're not. Talked to the HR woman this morning. No bending on their part at all. No matter what happens, for whatever reason, if I end up employed elsewhere (or return home because of an emergency and not work) I owe them everything within 2 years of my start date. They will not "gross up" anything. On top of which, when I do relocate my family and pay taxes on the value of the package, what's to stop Uncle Sam from refusing to repay me the taxes on money that I return to the company? Double Whammy!