I meant to respond to your question the other day but got sidetracked. Anyway, I'll bet they're asking about a criminal record going back up to 3 years. I doubt that they'll pay for a backgound check going back further on every single employee. (Was it in another state? If so, I really, really doubt they'd check all states, going back more than 3 years!)
(I can't believe I'm suggesting this but....) So I suggest telling a "white lie" and say you have a clean record. I don't see that you have a good alternative, if you don't want to come out to them in Central Texas. Good luck. Keep us posted. Lama