Well, this list shows 293 ZIPs that cross state lines [0], this FAQ says there are ~43,000 ZIPs in use [1] so that puts it closer to 99.3%.
But think about it, if you're taking an address to ship something, getting the ZIP right is what matters. If your package has 45201 on it, it doesn't matter if it says Cincinnati, OH or Cincinnati, KY.
[0] http://web.archive.org/web/20110112211559/http://maps.huge.i...