After having spend some hours on testing, we must conclude that it seems to be almost impossible to create a stable program that makes the NXT follow a line that curves both left and right by using bluetooth direct commands. We're using an approach that makes the NXT sweep first one way then the other, then double the distance and sweep again until the line is found again. The NXT's keeps on missing the line, and the amount of readings of the light sensor delays any other bluetooth commands to an extend which is not acceptable.
Therefore, we have decided to make the "Follow Line" program as a Lego Mindstorms NXT-G program, and execute it on the VM at the NXT. The result has shown to be very stable, and the fact that the execution of a program on the NXT still allows for direct commands over bluetooth to be received and executed. This is a feature which e.g. gives us the possibility of running the line following program on the NXT and then turning the NXT 180 degrees while the line follower is still running.
We shot a short video of two NXT's using the line following program: