Tell them you need a vector version of their logo - this can be an eps or pdf but must be vector.
If a vector version is not "available", tell them you need a high resolution (at least 1 MB) version for tracing, which will cost $45-$75 depending on complexity.
Another reason we go the extra mile is that we explain that once the artwork is in our computers the way we need it, the next time they order something the process is less costly, much quicker and easier. Everybody loves easier, faster and cheaper.
That not only gets them nearly every time, but it also cements it in their minds of who exactly to come back to for their next project or re-order.