What I really had in mind is that we use the existing levels as layouts, and just edit those. If we change them enough, we could say that they are inspired by the original levels, and that would not be illegal.
But the legality isn't the only reason why I would like some changes to the levels themselves and not just enemy count and such.. I really think it's almost impossible to make those levels very hard without changing them quite a lot.
At least I failed when I tried, they became harder but not really hard

So if anyone's interested, I would really like to make this a reality. The difficulty level bothers me a lot every time I play that game, it could be so much better if only it was more difficult.