Is it possible to drive a HDMI output without exact clock frequencies (74.25 MHz, etc.)?
The thing is, once you go outside the spec, anything can happen (and usually does on a major customer demo!).
You might get it to work, sort of, sometimes, but as soon as you break spec, you are responsible for whatever does not work reliably.

I am not at all surprised that some monitors work and some do not, IME it is usually the computer monitors that are fussy while tellies will often take any old rubbish. 

There are about half a dozen or so sets of frame timings that pretty much everything accepts, basically the broadcast derived ones, but they tend to need that clock that you don't have, and yea, EDID is often best ignored (or at least taken with caution), buggy does not begin to describe some of them.  

One gotcha is to check the sound, as the dividers to derive the 48K audio rate from the pixel clock will be off, and that may cause issues.

Time for a board respin?