Well, I don't know if you have to do this with the data in-place or if you can create a new output feature class with the results and then just link it back to your original dataset. If you can create a new feature class in the process of accomplishing this job, then the thought that comes to my mind would be to use the Spatial Join geoprocessing tool. What I would do in this case, first off, is check and make sure you have a unique identifier for each feature (other than the ObjectID or GlobalID fields); if you don't have such a field, no worries, just add a field to your main dataset with the field type of long integer and run the field calculate tool where the new field you created is set to the value of the objectid field. Then you would use that spatial join tool: join the parcels feature class and the counties feature class spatially, which if set up correctly should add the attributes, including name, of the counties feature class, to each parcel (leaving existing parcel attributes) and write all of that to a new output feature class. Then you could do a select by attribute on that new feature class to select all of the features where the parcel's county field is not equal to the county's name field. Then, if you really wanted to, you could extract those selected records to a new feature class or just a new table and then join that to your original parcel feature class so you could do a sort, select statement, etc... on your original feature class to get the specific records you need or do what you need with them. Personally, if you're going to try doing this and you're not sure about coding it in ArcPy directly, try using model builder (can be accessed from arccatalog or arcmap) and set up the operation that way, where you can drag-and-drop geoprocessing tools, feature classes, etc... . Then you can just select the option within model builder to export to python script.
Conceptually, it would probably look something like (this is just pseudo-code):
(Assuming unique ID field already exists, don't use OID or GlobalID as these can be different than their original values in an exported dataset or newly created dataset such as the output of spatial join)
Spatial Join (Target: Parcels, Join: Counties, Join Operation: One to Many - this
allows parcels in multiple counties to be identified, field map: set up as
applicable for your data, others: defaults or as needed for your situation)
Select (Input: output from spatial join, Expression: ParcelCountyName <> CountyName)
This isn't necessarily perfect, depending on what you need, but figured I'd share in case it helps. Also, FYI: I'm using v10.1 to write this, so minor modifications may be needed if you're using a different version.