You don't mention Python, arcpy, or any coding in your tags, so I would assume that you're limited to working in ArcMap; is that correct? I have a Python/ArcPy function that creates Thiessen polygons on the vertices of each polygon, which mostly yields the results that you're looking for.
The steps are basically:
1) Delete all extraneous fields (as step 3 creates a feature for each vertex, and you can quickly run out of memory if you keep too many attributes). You only want to keep whatever unique identifier field you're using for your polygons. Note that you probably want to make a copy of the original polygon feature class before doing this so that you retain all your attributes.
2) Densify your features to whatever XY tolerance you wish to apply. This will impact the accuracy of the result such that densifying to the feature class' XY tolerance will yield the most accurate results possible, but it may be computationally unfeasible.
3) Run the FeatureVerticesToPoints tool, which will create a point for each vertex in your input polygons.
4) Create Thiessen polygons from your points.
5) Dissolve the Thiessen polygons by your field(s) of interest--your unique identifier.
6) Erase your original polygon layer from the dissolved Thiessen polygons
7) Merge the erased Thiessen polygons with your original polygon layer
8) Dissolve based on your unique identifier field
I'm sure I didn't make that clear enough; let me know what you need clarification on. It makes more sense in code.
Here's an example before and after:
What this method does not do is follow the trajectory of a line to close off a polygon, so you may get unexpected results in some places: