If you deleted the files, they are gone. You can look into professional data recovery services ( like
www.drivesavers.com ), but they are pricey, and no data recovery is guaranteed. Since you've already written over some of the files, your chance of a full recovery is lower than it would have been had you simply erased the files. The longer you use the drive, the less chance of being able to recover the files.
No, the iTunes Music Store will not allow you to redownload your lost songs for free. You must repurchase them. You can try contacting them about this, but don't be surprised if they simply say, "No."