Vaital Deul, from the late-8th c, is a Devi (Durga) temple with a unique design. The sanctuary is rectangular as opposed to square, and so the tower above it is elongated. The topmost portion of the tower is heavily reconstructed. The mandap is also different, with shrines built into the four corners. Other than that the mandap is similar to the Parashurameshwar mandap. The only other place I’ve come across a mandap like this (with shrines on the corners) is in the Madhukeshwara Temple at Mukhalingam in Andhra Pradesh, which is an Odia style temple from the 8th c.
The rectangular-plan tower style is known as Khakhara Deul in Odisha, and is seen in Devi temples in the state. The Teli ka Mandir temple (also 8th c) at Gwalior Fort in Madhya Pradesh is famous for a similar tower. From the sides, the sculptural compositions of these two towers have a lot of similarities. One of the shrines at Nareshwar (near Gwalior) also has a Khakhara Deul tower (the photos of this shrine are close to the end of the Nareshwar post), though that is a much smaller structure. The three amalakas (finials) at the top of the tower of Vaital Deul make me wonder if this temple was originally designed to house three Devi idols representing Tridevi, hence the elongated sanctum.
From the photos below, we can see how close modern constructions are to these historic gems. Many of these temples in Bhubaneswar need to be given more space around them.
Vaital Deul
Right next to Vaital Deul is the Shishireshwar temple (also late-8th c), tightly squeezed in by modern-day constructions. It follows the scheme of the Parashurameshwar temple type. The sanctum tower is very similar in style to the contemporary Markandeshwar temple.