The Middle of What?

[The Might]

No, no, Middle-earth really was in the middle.
Please note that initially Middle-earth was created as a perfect land with a north-south line of symmetry.
M-e was lying right between the two great seas, Belegaer in the W and the East Sea in the E. Symmetrical Aman liead W of Belegaer and the Land of the Sun laid E of the East Sea.

But, as we know Melkor just couldn't help break the symmetry.
I just found this picture of Arda in those times from Mrs. Fonstad's Atlas of Middle-earth:



And even later M-e still was in the middle, you can see more or less good maps in the Atlas or the Encyclopedia of Arda.

EDIT: Sorry if there is copyright problem with the picture, I can only provide the link if necessary.