What is the most reliable and fault tolerant way to integrate 3rd-party data structures via a web service in Drupal 7?
1. Reformulating the question

Your example suggests that the data is read only on the Drupal side, with one-way syncing only. I think this is the most important factor to consider here, because in effect whatever solution you implement will be a variant of remote storage, syncing and local caching - even if the local caching ends up being entities in the Drupal database.

So the question, rather than being "local storage vs remote storage" is going to be:


Should you cache the data locally at all ;
Should you cache the data as actual entities, and use Feeds (or similar) to synchronise the data regularly ; OR
Should you use some custom made module that provides the syncing and the caching.


An article you might be interested is in "Remote Entities in Drupal 7".

2. Caching the data

In general, caching the data is a good idea:


You are protected against outages of the other services, or timeouts
in the connection ;
Having your data present in your Drupal database will speed up operations ;
Having your data present in your Drupal database will mean that you are more likely to get integration with other modules, such as Views (though this is not guaranteed).


The only advantage of not caching the data is that you never get stale data, which in some cases is preferable - sometimes it is preferable to display no data rather than stale data. I do not see this as a benefit in the example you have given, so I will focus this answer on a solution that involves local caching.

3. Local entities + Syncing

If you go for the option of having local entities and syncing them yourself, then we come back to your original questions:


Should you use nodes or custom entities ;
Which module is best for syncing.


3.1 Nodes vs Custom entities


The definition of what exactly is a node is one that is quite open. The documentation page on nodes suggests that nodes are "posting" that are "stored" on your site - neither of which apply to your data ;
As a Drupal developer I would expect that if something is a node then I should be able to manipulate it on the site itself ;
As Drupal user, I would similarly expect that nodes can be edited ;
This Drupal 8 issue https://drupal.org/node/2019031 suggests that the concept of "read only" is one that would apply at the entity level, rather than the bundle level. If this ever gets implemented you would benefit from it by having gone down this route.


To summarise: your data being read only and stored remotely it makes more sense to use a custom entity type to represent your data.

3.2 Syncing

For the second part, the two main modules for this are, as you suggest, Feeds and Migrate.

The difference between Feeds and Migrate is that Feeds is build for regular importing of content, while Migrate is build for one-off porting of content from one place to another. Migrate does support updating existing data, however given that both modules are well supported it makes more sense to use the module that was build for the task at hand - Feeds is a better match.

Having used both modules myself (Feeds for syncing, Migrating for migrating) I do not find Feeds to be more messy than Migrate. Migrate has required more custom code in my experience, though migrating entire sites is more complex than importing single content types, so it's hard to compare.

4. Custom module for remote storage, syncing + caching

There are a number of modules out there that can help with this task.

You mentioned the Web Services Data module, and others have mentioned the Data module. Another option to consider is the Remote Entity API module. Note that the only one of those I have experience with is the Data module.


The Web Services Data module does not yet have a release - which may indicate the code is not yet stable, the API might change and so on. It does not support Entity Field Queries (according to it's project page), and a quick browse of the code repository shows no evidence of it having Views support - so you would not be able to use Views to display your entities ;
The Data module is more oriented, in my experience, towards non-developers who have data in a table and want to expose it to views. I have found the Drupal 6 version to be quite frustrating to use - though that might have changed since then ;
The Remote Entity API module sounds quite promising - it supports fetching and caching of remote entities, and has Views support. It's only on alpha release - so API might still change. At first glance it does not seem to have Entity Field Query support either, and it only support one type of remote service so you would have to implement your own.


Conclusion

Given that none of the remote storage modules support Entity Field Queries, using actual entities + feeds is the solution that will give you the best integration with your Drupal site.

If Views support is enough, and you are not worried about potential integration with other modules via Entity Field Queries, then using the Remote Entity API might be the way to go - you would need to implement your own remote interface however.