Can an ID in a lookup field ever be invalid? Anywhere?

It is possible that I can read an ID from a field, and when querying for the item with the given ID I find no result. This will happen when Sharing Rules prevent the user seeing the item and the code is running "With Sharing".

The Sharing-ness of the code switches depending on the call tree, so as code enters a class that is marked with or without sharing permissions change. The permission does not change when execution enters a class that does not have a with or without sharing declaration.

Code generally runs Without Sharing, so this problem is only likely to occur if "With Sharing" has been explicitly turned on somewhere. (Or if the user calls anonymous apex). Trigger code starts Without Sharing, even if the code which called the DML was With Sharing.

For Sharing see Salesforce documentation on Sharing keywords.

Any value you observe in a lookup field will resolve to a live database record that can be referenced. The instant a record is deleted, all lookups will return a null value instead of the previously referenced ID value. Therefore, it is safe to assume that any ID value you observe in a lookup field is a legitimate record. However, just because the user can see an ID value doesn't mean they have the right to update that record, so one must always check for database save errors by exception or by partial save.

There are times when an ID value may be invalid, such as when a developer uses a text field to store references instead of lookup fields. For example, to store a reference to an event, you can't use a lookup field, so you'd have to necessarily use a normal text field. Opportunity Line Items are another example; in fact, many standard "detail" records can't have a lookup assigned to them. In this case, it's usually better to query before you update, although it's not required, because the database will still inform you of invalid ID values during a create or update call.

However, there is one specific use for querying records before updating: if you're worried about concurrency, it is highly adviseable to at least perform a SELECT ... FOR UPDATE command to force those records to be locked, granting your code exclusive access to those records for the duration of the transaction. This reduces the possibility of your values being overwritten at the same moment that another user is trying to modify those same records.