Simultaneous Localization and Mapping (SLAM) is one of the classical problems in mobile robotics. The task is to build a map of the environment using on-board sensors while at the same time localizing the robot relative to this map. Rao-Blackwellized particle filters have emerged as a powerful technique for solving the SLAM problem in a wide variety of environments. It is a well-known fact for sampling-based approaches that the choice of the proposal distribution greatly influences the robustness and efficiency achievable by the algorithm. In this paper, we present a significantly improved proposal distribution for grid-based SLAM, which utilizes whole sequences of sensor measurements rather than only the most recent one. We have implemented our system on a real robot and evaluated its performance on standard data sets as well as in hard outdoor settings with few and ambiguous features. Our approach improves the localization accuracy and the map quality. At the same time, it substantially reduces the risk of mapping failures.