Is there a chance that you are doing these operations in the same data frame as other data? I would suggest you create two new data frames and place each file into its own data frame with no other data. Then ... for each file, in its own data frame...you right-click on the layer, go to properties and determine the extent values. These will not change regardless of what you have done to the file in terms of defining a projection. Do the extents look reasonable? A file with a geographic coordinate system ( like a GCS WGS84) will only have values in the range -180 to 180 EW and -90 to 90 NS. If they are big numbers then you have projected data and the range in values will give you what type of projection it was or should be in. Ideally, both files should have the same extent if indeed they covered the same extent. If they have the same extent and they are defined differently, then one or both have been improperly defined when using the Define Projection Tool.
Now on to projection... When you use the Project Tool, always put the result into its own dataframe since a file that is projected will project-on-the-fly to try and match the projection of the dataframe...and as you have noted, when the file was defined wrong, then projected, it flies off to somewhere you don't want it to be.
The whole process of adding data to a data frame since ArcMape is to try to "be helpful"... In the "old days" you would get the warning that things didn't match and sure enough, the files would fly off into their corners spatially separated because the projection files were wrong, undefined or mismatch. In order to fix this in the "helpful" environment, you need to examine their properties...understand their possible extent values for a given coordinate system/projection and then act accordingly.
So in summary, I have no clue what the real coordinate systems of the input files were, but IF they were defined by some other source and they were redefined correctly...set them back and ensure that they are correct. Once they are in a know, verified coordinate system...you can proceed to Projecting the data to a different coordinate system. Then...and only then...do I introduce other data into the dataframe. If all the files play nice...then they should overlap or abut perfectly.