It's not clear to me exactly what your goal is, but it's very unlikely that you'll be able to achieve it without modifying the HTML. The only downside to modifying the HTML is the time required to do it. You don't have to put every <img> in a <div>. You might well find all that's required is to add a class attribute to the images that need to resize automatically, but that would also allow you to remove 'width' and 'height' attributes so the ultimate size of the file shouldn't change substantially. In any case, I doubt you'd ever reach a file size that would be a problem for either users or the search engines.

It sounds like the images are currently not in any kind of container, just mixed in with text? No <p> and no <div> in your page? Are these in tables? I think I'm missing something.

The CSS:

img { max-width: 100%; }

does not make the image fill up 100% of the available space, it makes the maximum size of the image the maximum size it can be which depends on what size the image is (unless it is forced to other dimensions). A 250px image can only be 250px wide at max-width of 100%. A 650px wide image has a maximum of 650px at 100%. The CSS as shown will reduce the size depending on the size of its container. If the container is a fixed width of 650px, it won't resize gracefully with a browser window. The excess can be hidden or it may have horizontal scrolling.

Too much depends on the css for the surrounding elements and what those element are, but rainborick is right in that you can't usually fix html pages without making changes. If you use a good text editor than can edit all files with find/replace it can make the job easier.

You could use:
img{
width: auto;
max-width: 100%;
}

{height: auto} is what you really need, or else anything with explicit height and width declarations will give you Unintended Consequences on narrower viewports.