Assuming all the air bleed ports on the top of the carburetor are clean, I would suspect the step up rod/piston/spring combination. I've run into this problem in years past but in retrospect think it was usually with an engine that had seen a cam change. That would affect the vacuum pulled at any given RPM. Take the access caps off, pull out the step up rods and see if the pistons and rods look clean yet.
I'm not clear on if this combo had been running right for you before, and just recently developed this problem. In theory at least, the AVS would have been tuned properly when made for the combination it was going to be installed on. You can do some rough tuning by changing the step up rod springs, to see if a stronger spring would richen things up a bit and make it run better at cruise, since I agree it sounds like a lean condition.
The secondary's, like you're used to on Holley's, are vacuum activated, but use a completely different means of opening, and counterweights to close back up. It would be pretty easy to check that they move freely reaching down through the top of the carb with a screwdriver (and the carb pulled to the wide open throttle position, engine shut off of course) That said, I've chased a lot more secondary opening problems with Holley's over the years than AVS or AFB's.
As mentioned, an air/fuel meter would remove a lot of the guess work, but does involve finding a shop with the right tools, experience (and motivation) to tackle the problem.
One other thought, which is sure to get someone here excited, is to enlarge one of the bleeds inside the primary assembly, which can be removed from the top without much trouble. I had been told years ago that the current fuels required a slight enlargement of this port in order to improve drivability. I have to do some digging to get you the specifics and I know I have a drill bit of the right size. I can tell you I made this change to the AVS on my 69 Roadrunner and it helped improve drivability for me. Others will tell you it's a band aid fix for another problem. I don't know, I just know it cured my hesitation problem. I've been running the car for a number of years now without any other issues surfacing from the change.
I'll be quiet now and others much more experienced and smart than me add to the discussion.