(Warning: Shameless plug ahead)
Not sure about ICP, but you could also try hector_mapping and see if it works better. We normally get good results with the Hokuyo UTM-30LX scanner and similar scenarios like that shown in your video.
/edit: Updated results with hector_mapping. I found that increasing the scan queue size from 5 to 25 gets rid of all errors, resulting in nice map without inconsistencies. It's a interesting question why that is though, considering that it takes only 4-8% of CPU (probably idling waiting for transforms). Map looks like this:
The results can be reproduced using this launch file. Similar to this tutorial, just start the launch file in one terminal:
roslaunch hector_slam_launch postproc_qut_logs.launch
and then play back your bagfile in another terminal:
rosbag play 2.5D_bag02.bag --clock