This is most certainly by design, it should be impossible to move a page if the page is published to a specific location.
You have three options - the third one I wouldn't do, but it's there:
1) Unpublish the pages and then move them to the desired location, then republish
2) Create copies of the pages and publish them - then simply unpublish and delete the original pages.
3) Not recommended, but letting you know what's possible - It's possible to rename the structure group paths and then republish the pages
I certainly recommend option 2 as the safest way, but this could raise some questions on the implementation too.
Also, if you've changed publication target configurations over time, the 'published' flags could be messed up. Have look at this question for more: https://stackoverflow.com/questions/10934210/tridion-the-item-is-published-unable-to-delete-page-error-when-page-has-bee