Configuring DNS for new web host while keeping old mail server
Solution 1:
Indeed you need to REMOVE the wildcard DNS and just manually enter all of your subdomains minus as you mentioned the mail. one. Which that will need to point to the current mail server as you mentioned.
From there you should be set.
I would however STRONGLY consider a non EIG provider though. There are many SMBs within that price that can likely give you better web service, customer service, etc.