Deputy Phil Barney of the Sevier County Sheriff's Office was operating a stationary radar on Interstate 70 at the Sigurd, Utah, interchange at approximately 7 a.m. on June 23, 1993. He was positioned facing westbound in the center of the median. Deputy Barney observed a white Buick traveling eastbound and straddling the lane marker as it approached. The vehicle was directly in the center of the center line and straddled it for about 100 to 150 feet (or for about one second) before it proceeded into the outside lane of traffic. Deputy Barney observed that the driver of the automobile was African-American and that the car had a California license plate. He then immediately turned his vehicle around and pursued the African-American driving the Buick with out-of-state license plates.

Deputy Barney testified that straddling the line was not clearly a violation of the law, except for possibly being an improper lane change for failure to signal.1 He did, however, consider this conduct to be indicative of a sleepy or intoxicated driver. His purported concern was that the driver of the Buick with out-of-state license plates might be sleepy or intoxicated. Deputy Barney saw no further driving irregularities as he pursued and pulled over the driver of the Buick.2

As he approached the vehicle, Deputy Barney testified that he noticed that two African-American people were seated in the front of the Buick. According to the video, he arrived at the driver-side car window at 7:08:30 a.m. He asked the driver of the car, Appellant Terry Louis Lee, for his driver's license and the vehicle registration. Deputy Barney testified that he initially smelled alcohol emanating from the car, but he did not ask Mr. Lee whether he had been drinking. He did ask, however, whether they (Mr. Lee and the passenger in the car, Mr. Gregory Lacy) had been driving all night. Mr. Lee responded that they had not been driving all night, but had stopped at a rest stop.

Mr. Lee presented Deputy Barney with his California driver's license, but was unable produce the registration. Deputy Barney then asked if the vehicle was leased. Mr. Lacy responded affirmatively. Deputy Barney then asked if they had the lease agreement. Mr. Lacy responded that he did not. Deputy Barney asked to whom the vehicle was leased, and Mr. Lacy responded that it was leased to himself and his wife. Deputy Barney asked if he had a yearly lease. Mr. Lacy responded he had a monthly lease.

Deputy Barney then asked Mr. Lacy for identification. Mr. Lee asked Deputy Barney why he had pulled them over. Deputy Barney replied that they were straddling the line and he thought that they might be going to sleep. Mr. Lacy then stated that he had the lease agreement in the trunk. Mr. Lee and Mr. Lacy then proceeded to exit the vehicle and open the trunk.

While retaining Mr. Lee's driver's license, Deputy Barney asked where they were traveling to. Mr. Lacy stated that they were going to Denver. He then presented to Deputy Barney a California identification card and prior lease agreements from Enterprise Leasing. Also, Mr. Lacy was not carrying a driver's license, and there was some question as to whether he had been driving. Mr. Lee stated that they had not been trading off, but they had stopped to rest.

Deputy Barney testified that, at this point, he was certain that the smell of alcohol came from Mr. Lacy. He then asked both Mr. Lee and Mr. Lacy if they consumed any alcohol, and they replied "no." Then Mr. Lacy appeared to indicate that he had but that he had been sleeping and not driving.

Deputy Barney returned to his patrol car and ran computer checks on the vehicle and on Mr. Lee and Mr. Lacy at 7:13 a.m. The video tape is blank for more than ten minutes from 7:14:04 a.m. to 7:24:45 a.m. The tape stops with Officer Barney calling in for the computer check, and it resumes with Mr. Lacy approaching Officer Barney as he is sitting in the patrol car and writing out a warning citation for improperly changing lanes. Officer Barney testified that the check indicated that the vehicle was not reported stolen and was owned by Enterprise Leasing. The background checks revealed criminal records for both Mr. Lacy and Mr. Lee.

As Deputy Barney finished writing the warning citation for improperly changing lanes, Mr. Lacy approached the patrol car and asked Deputy Barney where the nearest rest stop was located. Deputy Barney told him that the next town was nearby. Mr. Lacy provided a detailed account of his travel plans and his history of, and reasons for, renting cars from Enterprise. He said they were going to Colorado to meet his sister, and they were going together to visit their mother in Oklahoma. He explained that he was having problems with his own car and that he had rented the Buick to have a larger car for his trip. He said Mr. Lee had drunk too much coffee and that he had been snoozing while Mr. Lee was driving.

Then, suddenly at 7:27:10 a.m., Deputy Barney asked Mr. Lacy if they were carrying any firearms. He responded that they were not. Deputy Barney then asked if they were carrying any narcotics. Again, Mr. Lacy replied that they were not. At 7:27:20 a.m.--more than nineteen minutes into the "brief" Terry detention--Deputy Barney asked if he could search the car. Apparently taken aback by the question, Mr. Lacy replied, "Sir?" Again Deputy Barney asked, "May I search your car?" Mr. Lacy gave him permission.

Deputy Barney returned to the Buick with Mr. Lacy. As they walked to the car, he asked Mr. Lacy if he had ever been arrested. Mr. Lacy admitted that he had been previously arrested. At the car, Deputy Barney asked Mr. Lee to step out of the car. Then Deputy Barney returned the rental documents and identification card to Mr. Lacy, and he handed Mr. Lee his driver's license and the warning citation. At 7:28:30 a.m., a back-up officer, State Trooper Hillen, arrived.

Deputy Barney had Messrs. Lee and Lacy move to the rear of the Buick where he asked Trooper Hillen to watch them. Deputy Barney then proceeded to lean into the front driver-side of the Buick. At 7:29:24 a.m., the tape ends with Deputy Barney emerging from the vehicle and moving toward the back of the vehicle.

Deputy Barney testified that he searched and found nothing under the driver's seat. He then reached under the front passenger seat and retrieved a shaving kit. He unzipped the kit and found a large clear plastic bag containing a substantial amount of crack cocaine on top of other items. Both Messrs. Lee and Lacy were placed under arrest.

Codefendants Lee and Lacy were indicted for possession of more than fifty grams of crack cocaine with intent to distribute. Both Defendants filed a motion seeking to suppress the evidence seized from the vehicle. After a hearing, a magistrate judge recommended denying the Defendants' motion to suppress, which was adopted by the district court. Defendant Lee pled guilty to possession of five grams or more of crack cocaine in violation of 21 U.S.C. Sec. 844, while preserving his right to challenge on appeal the denial of the motion to suppress. Defendant Lee has been sentenced to ninety-six months imprisonment to be followed by three years of supervised release.

Appellant raises three issues on appeal: (1) whether the traffic stop was merely a pretext to conduct a search of the defendants' vehicle; (2) whether the traffic stop was not justified at its inception and was not reasonably related in scope to the circumstances surrounding the stop; and (3) whether defendant's consent was the fruit of an illegal detention.

"[T]he ultimate determination of reasonableness under the Fourth Amendment is a question of law which we review de novo." United States v. Fernandez, 18 F.3d 874, 876 (10th Cir.1994). Under Terry v. Ohio, 392 U.S. 1, 21, 88 S. Ct. 1868, 1879-80, 20 L. Ed. 2d 889 (1968), a law enforcement officer is permitted to make a limited "seizure" of an individual suspected of criminal activity if the officer has "specific and articulable facts which, taken together with reasonable inferences from those facts, reasonably warrant that intrusion." We review Terry stop encounters in a step-by-step manner because what may begin as a routine traffic stop will often escalate into probable cause for a search or a search pursuant to a consensual encounter. We examine each stage of the encounter to ensure that the government had the required amount of reasonable suspicion, probable cause, or consent to support the search.

Pursuant to Terry, we make a dual inquiry in determining the reasonableness of an investigative detention. 392 U.S. at 20, 88 S.Ct. at 1879. First, we are supposed to examine "whether the officer's action was justified at its inception." Id. While the stop in this case appears to be clearly pretextual, our inquiry into the officer's justification is severely limited by our recent decision in United States v. Botero-Ospina, 71 F.3d 783 (10th Cir.1995) (en banc). Under Botero-Ospina, "[o]ur sole inquiry is whether this particular officer had reasonable suspicion that this particular motorist violated 'any one of the multitude of applicable traffic and equipment regulations' of the jurisdiction." Id. at 787 (quoting Delaware v. Prouse, 440 U.S. 648, 661, 99 S. Ct. 1391, 1400, 59 L. Ed. 2d 660 (1979)). The facts in this case are almost identical to Botero-Ospina. In each case, Deputy Barney had pulled over a non-Anglo motorist for crossing over the center line. As in Botero-Ospina, Deputy Barney found that straddling the lane marker constituted an adequate basis to investigate for impairment of the driver due to sleepiness or intoxication.3 Thus, Deputy Barney's purported concern that the Defendant with out-of-state license plates might be sleepy or intoxicated because he had changed lanes is sufficient to justify the stop under Botero-Ospina.

Our second inquiry under Terry is whether the officer's action "was reasonably related in scope to the circumstances which justified the interference in the first place." Terry, 392 U.S. at 20, 88 S. Ct. at 1879. The Supreme Court has instructed that an investigative detention must "last no longer than is necessary to effectuate the purpose of the stop," and "[t]he scope of the detention must be carefully tailored to its underlying justification." Florida v. Royer, 460 U.S. 491, 500, 103 S. Ct. 1319, 1325, 75 L. Ed. 2d 229 (1983).

In this case, the scope of Defendant Lee's detention was not carefully tailored to Deputy Barney's purported concern that the Defendant was driving while sleepy or intoxicated. Deputy Barney asked for Mr. Lee's driver's license and vehicle registration. Deputy Barney stated that he initially smelled alcohol emanating from the car, although he did not ask Mr. Lee whether he had been drinking. Deputy Barney asked whether the Defendants had driven through the night, and Mr. Lee responded that they had stopped at a rest stop. Mr. Lee produced a valid driver's license, and Mr. Lacy explained he did not have his lease agreement. Deputy Barney determined that the car was not reported stolen and that it was owned by Enterprise Leasing Company. Mr. Lacy provided enough documentation to reasonably show that he and Mr. Lee were entitled to operate the car. Deputy Barney determined that the smell of alcohol was from Mr. Lacy and not from Mr. Lee. As Deputy Barney completed the warning citation, Mr. Lacy also provided a sound explanation of his travel plans. Deputy Barney then questioned Mr. Lacy about guns and drugs, and he asked Mr. Lacy for permission to search the car.

We have repeatedly stated, " 'When the driver has produced a valid license and proof that he is entitled to operate the car, he must be allowed to proceed on his way, without being subject to further delay by police for additional questioning.' " United States v. Sandoval, 29 F.3d 537, 540 (10th Cir.1994) (quoting United States v. Gonzalez-Lerma, 14 F.3d 1479, 1483 (10th Cir.), cert. denied, --- U.S. ----, 114 S. Ct. 1862, 128 L. Ed. 2d 484 (1994)). Deputy Barney's questions about firearms and drugs were unrelated to his underlying justification for the detention, which was to determine if the Defendant was driving while impaired. After determining that Mr. Lee was capable of driving, Deputy Barney should have terminated the encounter and permitted him and Mr. Lacy to go on their way.

After having his suspicions allayed, Deputy Barney could not further detain Defendants or search Defendants unless he had probable cause or their consent. The Supreme Court has explained:

[W]hen an officer's observations lead him reasonably to suspect that a particular vehicle may [be involved in criminal activity], he may stop the car briefly and investigate the circumstances that provoke suspicion. As in Terry, the stop and inquiry must be "reasonably related in scope to the justification for their initiation." 392 U.S., at 29 [88 S.Ct. at 1884].... [H]e may ask them to explain suspicious circumstances, but any further detention or search must be based on consent or probable cause.

United States v. Brignoni-Ponce, 422 U.S. 873, 881-82, 95 S. Ct. 2574, 2580, 45 L. Ed. 2d 607 (1975). The next step, then, is whether, under the totality of the circumstances, Deputy Barney had probable cause to further detain and search Defendants. Deputy Barney, however, lacked "specific and articulable facts" to "reasonably warrant" shifting the focus of his intrusion from the traffic stop to guns and drugs. Terry, 392 U.S. at 21, 88 S.Ct. at 1879-80.

The government argues that Deputy Barney had an appropriate factual basis supporting probable cause for two reasons: (1) the Defendants were attempting to divert attention from the passenger compartment of the car by going to the trunk of the car to get Mr. Lacy's past rental agreements; and (2) the Defendants' extensive criminal histories gave rise to a concern that they possessed weapons. Appellee's Br. at 8. The first factual basis cited by the government is inappropriate and nonsensical because the Defendants' conduct in going to the trunk was innocuous; they went to the trunk for the purpose of obtaining past rental agreements, which in fact were in the trunk. The Defendants' intent in going to the trunk was to satisfy Deputy Barney's inquiry into their right to operate the vehicle. Some facts must be outrightly dismissed as so innocent or susceptible to varying interpretations as to be innocuous. Cf. Reid v. Georgia, 448 U.S. 438, 441, 100 S. Ct. 2752, 2754, 65 L. Ed. 2d 890 (1980) (conduct that "describe[s] a very large category of presumably innocent travelers" is insufficient to constitute a reasonable suspicion). The Defendants' conduct in obtaining prior lease agreements from the trunk to show they were entitled to operate the rental car is so innocent as to be innocuous.

Both Defendants have extensive criminal histories, but "knowledge of a person's prior criminal involvement (to say nothing of a mere arrest) is alone insufficient to give rise to the requisite reasonable suspicion" to justify a shift in investigatory intrusion from the traffic stop to a firearms or drugs investigation. United States v. Sandoval, 29 F.3d 537, 542 (10th Cir.1994). We explained in Sandoval:

If the law were otherwise, any person with any sort of criminal record--or even worse, a person with arrests but no convictions--could be subjected to a Terry-type investigative stop by a law enforcement officer at any time without the need for any other justification at all. Any such rule would clearly run counter to the requirement of a reasonable suspicion, and of the need that such stops be justified in light of a balancing of the competing interests at stake.

Id. at 543. The facts relied upon by the government are insufficient to create the probable cause necessary to justify Deputy Barney's search in this case.

Finally, the government asserts that Deputy Barney's search was valid because he obtained consent from the Defendants. Appellee's Br. at 9-10. We have consistently held "that an encounter initiated by a traffic stop may not be deemed consensual unless the driver's documents have been returned to him." United States v. Gonzalez-Lerma, 14 F.3d 1479, 1483 (10th Cir.), cert. denied, --- U.S. ----, 114 S. Ct. 1862, 128 L. Ed. 2d 484 (1994); accord United States v. Lambert, 46 F.3d 1064, 1068 (10th Cir.1995); United States v. Walker, 933 F.2d 812, 817 (10th Cir.1991), cert. denied, 502 U.S. 1093, 112 S. Ct. 1168, 117 L. Ed. 2d 414 (1992). In this case, Deputy Barney possessed Mr. Lee's driver's license and Mr. Lacy's identification card and rental documents at the time he asked permission to search the vehicle. Therefore, Deputy Barney's request to search the car was not a consensual encounter because the Defendants "would not reasonably have felt free to leave or otherwise terminate the encounter" with Deputy Barney because their documents had not been returned. Lambert, 46 F.3d at 1068.

Deputy Barney exceeded the scope of the Terry stop, and he seized the crack cocaine in this case without probable cause or the consent of the Defendants. Accordingly, the crack cocaine evidence is tainted fruit of an unlawful search and cannot be used by the government in prosecuting Mr. Lee. The judgment of the district court in adopting the magistrate judge's recommendation is, therefore, reversed, and Mr. Lee shall be permitted to withdraw his guilty plea.

REVERSED and REMANDED.