Just to put my input in, It does look to be a stolen phone and it has been listed. If you have the box for the phone you can simply compare the IMEI to the box and see if it is the same and if not they gave you another phone. Other side is the person who sold you the phone stole it from someone else and the original owner finally reported it.
There is a few apps out there that will and can change IMEI but you will have to do some hunting around for them. It will be pretty tough to obtain one that will function.
I have to say, I am surprised your so quick at trying soo many different Rom;s with the possibility of bricking the phone. Unless that is not something your worried about. Well anyways good luck.
Free to Roam:
X10a Rooted/Recovery 2.3.3 Ginger