Lost the private key for signing android apk. Can app be released to Android Market?

You are correct in that you will have to release this as a new application with a different package name. You will have to pull the other app from the Market as it will no longer be updateable and your users will have to redownload the new version of the app.

I don't see any reason why Google would have any issues with this, it's a known issue that some developers/companies can come across when they loose their signing key. Also, as far as I know, Google doesn't closely monitor incoming apps unless they are being flagged.

I've seen some apps that have 10 versions of the same app in the Market, just so that they can have more visibility, which is something that I think Google needs to look out for.