Try to learn to feel 4/4 so you don't have to tap your foot at all. This might sound extreme, but from now on for the rest of your life you should play to a metronome on 2 and 4 when you're practicing. It will become part of you at some point. Note: It's helpful to also practice w/ the metronome on other beats, for example "only on beat 2" or "only on beat 4." But as a basic point of reference I would recommend using 2 and 4"as your go-to metronome feel. I even use 2 and 4 when I'm practicing Latin tunes. Not all the time but often.
You mentioned Kurt's phrasing is hard to emulate in some places on East Coast Love Affair. I think that's because the tempo is so slow on that tune. It gives him a ton of space to work with, so when you break it down and look at the solo on paper, you end up with some wild stuff that might not be played exactly as written. It probably doesn't have as much to do with your time keeping as it does with Kurt's rhythmic phrasing.
You shouldn't have to tap your foot to keep time. At some point you'll get there if you practice w/ a metronome and play w/ musicians enough. I come from a rock and metal background too but I became possessed by the jazz demon about 7 years ago. I tend to feel everything half as fast as it really is. At a tempo like 240bpm I only think about the down beat on every other measure. If the song is really swinging hard I only think about the downbeat every 4 bars.
I agree with Sandemose: Good time is internal. Some people are gifted with it, others like myself will always have a weak sense of time. Obviously if you're a jazz player you're likely to be working on your time sense much more than the average musician, but I think some people just "have it."
Quintracy, that exercise you mentioned is really cool. I've always found it extremely difficult.