Bernd -- the trouble with anything done over standard HTTP is that it's plaintext; anyone can fake anything. IP Spoofing is a bit more challenging to do than just plain cookie stealing, so tying to the IP tends to be what people do. Like you said, that does not work very well with highly dynamic environments.
The only mostly secure way I can think of is to use HTTPS to place and verify a "permanent" cookie, and then place (in the same HTTPS session) a short-lived session cookie. The rest of the communication can be done over regular HTTP, using the session cookie to authenticate.
That way, fewer resources are used in supporting encryption (just the handshake), the permanent cookie is not exposed -- it's only transmitted under encryption -- and stealing the session cookie opens up to only limited risk, since that cookie will quickly expire.
All that being said -- don't let users click "remember me" on a site that contains truly sensitive data! That's why Banks don't do it..
Hope this helps.