The Sept/Oct 2009 issue of Robot magazine has an article on a very fast VEX line following robot.

There's a video of the robot at http://www.youtube.com/watch?v=05d3yb8VHmA It uses a PID control algorithm.. The robot runs at almost two feet per second. It was programmed in ROBOTC; complete source code is included as one of the sample programs that come with a ROBOTC download.

http://www.youtube.com/watch?v=T3xa_4GAkbY shows the same robot programmed with a basic “zig zag” algorithm. The maximum speed of this robot is about six inches per second before it is unable to follow the line.

PS. I wrote the article for Robot magazine.