Due to the shoestring budget, the search server is offsite from the database and the web frontend. This didn't pose an issue until traffic increased, and it began to put a strain on the link between the two servers.
The latest "fix" was to create multiple links between the frontend and the search server, and using a round-robin to probe the different connections. The errors were being logged as "unknown local index 'a_ancient' in search request", even though the index did exist and would return the correct result when queried again. I believe this is the result of a networking issue, and an unhelpful error message.
The downtime the past few days seems to be an issue with the entire VPS. Logging into the azure console to see what's going on with it this time...