Will a low-end dedicated server be enough for my application?
Solution 1:
Just to start with realistic goals, you're not going to get a dedicated server for < $85 a month anywhere. That said, it looks like some big optimizations could help you out.
Scott Hebert posted recently on Planet Sysadmin with a list of cheap VPS providers. http://slaptijack.com/it-management/cheap-vps-providers/
Have you considered pre-downloading these text files beforehand? If they change frequently, how about downloading them periodically and using the local cached copies? I bet a lot of your time is spent on the download, and not the processing.
Take a look at optimizing your regular expression queries, as well. grep can be very slow if it's an older version -- improvements of 10x can be seen by just going to a later version. http://savannah.gnu.org/bugs/?14472
It's always good to explain as much about the issue as possible. You say this is a Windows server, which may also bump up your cost considerably, as licensing isn't free.
Solution 2:
You should be able to get an unmanaged dedicated server core i7 of >2.3Ghz with 8GB of ram and 750GB disk, with some terrabytes of data transfer (reasonable bandwidth) for about USD65/month.
That said, if a single call requires a full 20 seconds (ie, 5 on a modern machine) you are in for some trouble if you get some traffic.
Is it spent waiting for the network of crunching CPU? It look like Jeff McJunkin has some good suggestions.
Edit For example: http://www.hetzner.de/en/hosting/produkte_rootserver/eq4/, (I have some with them, they are pretty much ok) - there are plenty of others.