Vision of the Oracle League reports in our forums that a Heroes IV Complete package might be available in time for Christmas in North America:

I went in to GameStop yesterday to see if preordering of H5 was available yet.
They said "Yep, here it is... Heroes 4 Complete, December..."
I said "Heroes FOUR Complete?"
Them: "Yeah, releasing on December..."
So, there IS a H4 Complete, wish I could remember the actual date it will be shipped.

Check out her post here. That's some good news, since getting the Heroes IV expansions on eBay was both difficult... and costly. Vision also linked to that listing of Heroes V on GameStop. The price is $49.99 and the expected release date is February 15th.