This paper presents a novel outlier rejection approach for feature-based visual odometry. The proposed approach is based on an empirical observation that shows that some 2D-3D correspondences with very low reprojection error can cause a high error in pose estimation. This work exploits such observations for odometry when a stereo camera is available. We argue that an explicit pose error measure is desired over that of implicit reprojection – whenever the former is possible – to classify correspondences into inliers vs. outliers for robust long-term odometry. To explicitly measure the plausible pose error, we derive bounds on the individual pose parameters with the help of the known orientation of stereo cameras. In this process, we formulate our bounds using the sum-of-square polynomials, which allow us to test whether a given correspondence satisfies any solution within the expected bounds. If the correspondence does not satisfy bounds for any parameter, it is considered to be an outlier. We implemented and tested the proposed method for the unmanned aerial vehicle (UAV) indoor navigation. The experiments from both benchmark evaluations (EuRoC and KITTI) and UAV onboard tests indicate that the inlier group refined by the proposed method significantly improves odometry estimation compared to the traditional outlier rejection methods. In fact, the proposed method performs as accurately as inertial measurement unit (IMU) aided methods in the state of the art. ROS project page (open-source code with demo video) is available at https://github.com/arclab-hku/SOPVO.