With ArcGIS you can use the spatial join tool (or in a script) to find which zip code polygons intersect with more than one state polygons. In the output feature class, there will be a Join_Count field that will indicate multiple states. You could do a similar thing with zips and cities. There will likely be false positives where the zips unintentionally overlap more than one because of border inaccuracies/lack or resolution. You could possibly do a negative -100m buffer of the zips before the spatial join and see what that does.
target_features = "C:/data/usa.gdb/states"
join_features = "C:/data/usa.gdb/zips"
out_feature_class = "C:/data/usa.gdb/states_zips"
arcpy.SpatialJoin_analysis(target_features, join_features, out_feature_class, "JOIN_ONE_TO_MANY")
"Two new fields, Join_Count and TARGET_FID, are always added to the output feature class. Join_Count indicates how many join features match each target feature (TARGET_FID).
Another new field, JOIN_FID, is added to the output when JOIN_ONE_TO_MANY is specified in the Join Operation parameter."