A particle filter based solution to the out-of-sequence measurement (OOSM) problem is proposed. The solution is storage efficient, while being computationally fast. The filter approaches the multi-OOSM problem by not only updating the estimate at the most recent time, but also for all times between the OOSM time and the most recent time. This is done by exploiting the complete in-sequence information approach and extending it to nonlinear systems. Simulation experiments on a challenging nonlinear tracking scenario show that the new approach outperforms recent state-of-the-art particle filter algorithms in some respects, despite demanding less storage requirements.