From my understanding of the caching mechanism, the response header Last-Modified, request header If-Modified-Since and etc has accuracy to the second, i.e. If-Modified-Since: Wed, 21 Oct 2015 07:28:00 GMT, and thus subsecond modifications would undermine invalidation:
12:00:00.100 /path/to/resource updated to Version 1
12:00:00.200 GET /path/to/resource from client A
12:00:00.300 Response: Version 1 of the page with Last-Modified: 12:00:00
12:00:00.400 /path/to/resource updated to Version 2
12:00:00.500 GET /path/to/resource from client A with If-Modified-Since: 12:00:00
12:00:00.600 Response: 304 Not Modified
# and even after time passes
16:15:00.000 GET /path/to/resource from client A with If-Modified-Since: 12:00:00
16:15:00.100 Response: 304 Not Modified
And until the cache expires, the client would not ever get Version 2 of the page.
Is this actually the case? Should versions stored in the page always increase the last modified date of the page by one second?
Yes, the one-second resolution of Last-Modified means that validation requests with If-Modified-Since can return the inappropriate value if the resource changes in less than a second. Your example is correct.
The specification acknowledges this, and gives rules for when a Last-Modified header can be considered a strong or a weak validator. You can read more about that distinction in the specification, but essentially it's saying explicitly that the validation could fail (be weak) unless the client or server can be sure that it won't (by comparing the Date and Last-Modified headers, for instance).
The solution, though, is not to lie about the Last-Modified time, but to use an ETag instead. It doesn't suffer from this sub-second resolution problem, and is explicitly recommended as an alternative in this case:
An entity-tag can be more reliable for validation than a modification date in situations where it is inconvenient to store modification dates, where the one-second resolution of HTTP date values is not sufficient, or where modification dates are not consistently maintained.