I have searched for this, and have found few informative threads.
I’m considering getting an old pixel (8 and up), rocking GrapheneOS, and using pre-paid sim cards for accessing data. But could my device somehow be formerly tied to criminal activity engaged in by the former user? Perhaps as identified through the IMEI? I’d be purchasing from a reputable reseller.
Am I just being way too paranoid here?
Yes:
That depends on your threat model.
Related:
Thank you for your reply. The link is really informative. And I recognize the thread you posted. Regarding my threat model, I’m jostle concerned about employers, both current and prospective, becoming aware of my pseudonymous political commentary online. I’d not love it if law enforcement figured out who I am either, as I’m quite critical of police.
This being said, I live in Canada, am doing absolutely nothing illegal, and when push comes to shove am not super worried about law enforcement. But I would be concerned if my IMEI is formerly associated with someone who was engaging in illegal activity. What I’m wondering is if that is such a low possibility that I may as well worry about catching a stray bullet or being hit by lightning.
Does this clarify my position?
Yes, you will need to decide whether the probability, regardless of whether it is low or not, is worth the risk. If not, acquiring a new phone would be a more appropriate solution.
Since @FranklyFlawless answered your primary concerns, I’m want to go for your second concerns.
Your phone’s IMEI won’t be nearly as big of a risk as you might think in this regards. Since you’re going for GrapheneOS, apps won’t have access to your IMEI, as per the GOS documentation. Sure, if law enforcement have your phone’s IMEI then they can track you with it, but it’s unlike they’ll get it by itself from anywhere; it’s not a data point that’s exposed first, usually.
I’d say the much more realistic risk is accidentally exposing yourself to the platforms that you use to voice your criticisms. If you accidentally give them any personal information, they can sell it forwards and start to build a profile on you. And any profile they can make on you can be requested by law enforcement via subpoenas.
Don’t use your name anywhere, be careful not to correlate identities between profiles, and don’t use your phone number anywhere (even if you believe it’s anonymous), because if they can get even that, you can kiss your hopes of anonymity goodbye. Since you’re here on Privacy Guides in the first place, just go over the forum and the knowledge base for any questions, tips & tricks you can find for staying private.
Good luck on your privacy journey 
If you use your phone like a “regular” phone, i.e. connect it to cell towers to make calls & use your cellular data, that phone’s location is known to the network at all times due to the structure of the network. The network simply must know to which tower(s) your phone is connected to just to route your calls and data to in order to provide your phone with connectivity. There’s no way around this if you want to use your phone like a “phone” as we have come to know them in the modern world.
Those cell towers your phone is connected to can then be used to locate your phone through a method called triangulation. You can read the detailed technical breakdown here if you’re interested. In pratice this means that as long as your phone isn’t in Airplane Mode, the location of that phone can be found out by the network. In urban areas with towers basically everywhere, the precision of that location can be really accurate, even down to a few meters inside areas that have good coverage.
Since your cellular provider can find your phone’s location and since your cellular provider is a company that has to follow the law, law enforcement can simply subpoena them for your phone’s location. They can ask where it was at what time on what date. I don’t know about your country, but in my country the cellular provides store the location information for who knows how long. There’s regularly news of people being convicted for crimes based on their phone’s location information that was gathered by the network at the time of the crimes. The info of everyone is recorded at all times here; maybe your country is different, maybe not.
Now, let’s say you have a pre-paid anonymous SIM that you bought with cash and waited half a year to activate. If you plan on using that SIM in a regular phone in a regular way to make calls & use data whenever you wish, those precautions don’t matter in the long run. If law enforcement want to figure out who owns that SIM & who is behind that specific phone number, they can simply track your phone’s movements over time.
If you’re the average person, your phone is most likely on you 24/7 and it’s connected to the cell network 24/7. Law enforcement can simply check where that phone is every night (i.e. where you most likely sleep & reside), where it is during days (i.e. where you most likely work), or they can even simply request surveillance footage of your usual grocery store around the time your phone entered the premises. The gist is, that if you use your phone as a “regular” phone like most people do, law enforcement can figure out who your number belongs to, even if you purchased the SIM itself anonymously. They can figure out that it’s you behind that “anonymous” SIM. All they need is your phone number.
The only way to avoid is not to connect to the cell network. The OS you use is irrelevant, be it GrapheneOS with its general privacy improvements or a new iPhone with Apple’s promises of privacy from the cellular network. If you phone is connected to the network, it can be tracked.
Purchase from a certified refurbisher if one’s available in your zip code.
Generally, refurbished Androids are okay, but if your threat model goes, “only trust Google hardware,” then non-certified refurbished Androids violate that guarantee.
Long discussion here (in case you hadn’t found it already): Refurbished
The Android OS distribution is but one part of the jigsaw. The general rule is, software (on its own) cannot prevent hardware attacks.