Different Apple ID contacts appear on my device
At some point somebody used your Apple ID on one of their devices (either OSX or iOS), or their Apple ID on one of your devices.  Or, somebody might have connected your or their iPhone in your or their iTunes in the past.

And things got mixed up.  If you don't have a local iTunes backup, there's not too much you can do to recover.  And if you have a local backup chances are that it was made after the damage was done.

Having had the same mishap in the past, I have a couple 1000's pictures of my wife's iPhone mixed up with my personal collection.

If this is not enough, chances are (albeit small) that one of those devices is still connected to your Apple ID and syncing is still going on.

My following suggestion might seem stupid and short sighted, but if I were you, I would


change my Apple ID password
Delete all contacts on your device(s)
Add all your contacts again from the beginning


I understand that, if there's a lot of data involved, adding your contacts piece by piece can be quite time consuming, but the effort might be worth it.

If you have access to a Mac, things can be facilitated quite a bit:


You can use the native Contacts app to export your current data
to csv, import it in Excel and manipulate chunks of data much
quicker.
Busy Contacts can do some of
this for you, and it also can sync with other online addressbook
services.  If you have your contacts in e.g. gmail this can fasten
the process.