Using random or structured packing may be an option in clean service applications, but in this case, packing would get blocked up easily. For this fouling service application (especially in the lower part of the column), suggest going for fixed or variable valve trays or bubble cap trays. Variable valve trays would give you better turndown. The trade off with valve trays when compared with packing in this case is higher pressure drop for valve trays. See if you can increase column overheads ejector capacity instead of going for packing.