It sounds like the constraints are setup, which is good. A few things to check:
1) Assignments -> Settings -> Fitter. Optimize Hold Timing should be on for at least I/O(All Paths will work too) and make sure multi-corner optimization is checked. I don't think this latter is on by default in many versions.
2) Double check the setup slack at the slow corner. To add ~10ns in the Fast is probably adding 20-25ns in the slow corner, depending on speed grade. If that's tight on setup timing, the fitter is just trying to split the difference.
3) Make sure there is no Fast Output Register = On assignment. (You would have manually done this, so unlikely). This would force it into the I/O, and as you said, the delay chain can't be large enough to meet timing.
4) A location assignment for the register far away from the I/O should do the trick, although you shouldn't have to do this. Highlight the register in the TimeQuest report, Locate -> Assignment Editor so the register name shows up in the To column, Location as the assignment, and do something like LAB_X1_Y1, for example, to put it in the bottom left corner.
5) A 10ns hold requirement is quite large. Usually when I've seen stuff like that, it's met by sending data out on the falling edge, which adds a half-cycle delay that is PVT invariant. Just an idea.