my experience (on windows xp, though i’m not sure if that matters) is that programs request access to midi devices on startup only. so, unfortunately, you need to restart max every time your setup changes (assuming you want to continue using midi).
a potential solution is to use a midi loopback driver (like midiyoke or maple) and use only the loopback port in max. since the loopback "device" is never disconnected, you’ll never have a problem with it in max. then you can have your keyboard route (via something like midiox) to whichever loopback port you’re using. so when you disconnect/reconnect the keyboard, you’ll only need to restart the routing program, and not max.