iTunes is not using the feed you linked to. It is looking for a feed at
This produces no result in iTunes: in a browser it produces the error you quote. You need to restore the feed to this URL.
The company hosting our podcast says their links are randomly generated (last four numbers) and can't be changed.
If they really are changing the feed URL every time - this is a bit difficult to believe - they are useless as a hosting company. iTunes needs a stable feeed URL. In order to change iTunes to a new URL you have to add a special tag to the feed it is using - the process is described here but if it's behavint the way you say that won't be possible.
You can ask Support to change the Store to a different feed by emailing therm at podcasts 'at' apple.com but I can't promise they will do this: and they certainly aren't going to do it every time you post a new spisode. I should find a hosting service that knows what it's doing.
It occurs to me that pssoblly you are labouring under the misapprehension that you have to create a new feed every time you add a new episode. This isn't the case (and if you do it, it will result in a new feed URL each time, obviously). You just add the episode to the existing feed and publish it, so the feed URL stays the same but it now includes an extra episode.
In that even you need to find out how to add an episode to the existing feed, and you will still either have to email podcasts 'at' apple.com and ask them nicely to change to the feed you are now using - either that or resubmit it as a new feed, which will necessitate changing the title slightly.