Jakob Larson You mention that your map is in NAD 1983 CA State Plane (zone ?) When you check the data that is being added to the map, what is it's coordinate system (before you used Define Projection)?
At first glance, this does look like a datum shift, though its interesting that there are three shifts, and I'm not sure if that could be because you used Define Projection before the screenshot?
Anyway, if the data had a coordinate system from a different datum than the map (say NAD 1927), and you don't apply a transformation, you'll see this shift. You'll probably want to go into your project Options > Map and Scene and enable the 'Warn if transformation between geographic coordinate system is required to align data sources correctly' option.
If the data that you're receiving has a coordinate system defined, we should assume it is correct until proven otherwise. That means that you should not use Define Projection—Data Management toolbox | ArcGIS Desktop "The only use for this tool is for datsets that have an unknown or incorrect coordinate system defined."
It is good practice to project all data into the same coordinate system so that you aren't projecting on the fly especially when editing or doing analysis. So using the Project—Data Management toolbox | ArcGIS Desktop tool is good. From first glance here, it looks like you'll need to apply a transformation in the tool. Did you do that?
If all data is projected into NAD 1983 California State Plane (same zone), and that is what the map is in, there will no longer be a need to apply a transformation to the map, and even if you have that option enabled, you shouldn't get any warning.
I hope this info is helpful. If you're still seeing issue lining up the data, send some more info about what the original coordinate systems are (again, before you've used Define Projection on them).