Like iball, I have a N800 and I use the ThinkOutside Stowaway Keyboard with mine. I've never had to re-pair the TOSK with mine despite many foldings.

I did have the same issue as what you're describing when I was using it with an older Palm. I don't recall what the issue was and it might have gone away on its own. It wasn't a lingering problem.

Have you tried changing the batteries in your keyboard? It might be losing the security key when it gets turned off. Aside from that, I can't think of what else it might be.