I was told on the phone that we need to send a letter to PAYE and SE with all the information of the whole situation for them to investigate this.
You need to do exactly as they have advise, ideally providing whatever proof you can or categorical statements - eg i would only ever get salary paid into bank account x - and it should be easily confirmed by this entity that payments have been paid to an account other than mine (presuming paid by bank).
Also advise that unless they provide contact info for company you cannot sort queries direct with that company to confirm what the situation is.
Be clear and frank that unless this company has paid cash which is unlikely you are presuming you hmrc and relevant company can prove between yourselves where funds have been paid and that isn't to you (unless that can show evidence otherwise)
In the meantime ask them to respect the taxpayers charter and not presume something is X when it may be Y, they should be well aware mixups do happen
We’ll presume that you’re telling us the truth, unless we have good reason to think otherwise.
Obviously you want to be pretty certain you haven't had any such paye income or sole trader income accidentally paid under paye - including the possibility of cashed in pension that could be mis-classified as salary - any such cash-in would be taxable as salary though
Note with regard to names these can often be misleading so a quick internet search may have taken you to the wrong organisation in that regard.
starting with details of bank account paid to seems like most logical starting place - although it could get messy if someone has the same name as you - even then the bank should be able to confirm hopefully that other details are different.