We got our Schengen visa from the Italian embassy. The bookings that were used in the submission for the visa had had to be cancelled as they were provisional and since the visa took time (received just 2 days before our travel date) they were all expired. We therefore had a short time left and made an entirely different itinerary, going to Austria, Hungary and the Czech republic.
At the airport we were denied boarding the flight to Austria by Austrian airline staff. They asked for our itinerary and we told them the truth: since the visa was delayed we had changed the program at the last moment, indicating that we would still be going to visit Italy once we entered via Austria. They asked us to wait until they could confirm with an Austrian border police representative. The airline staff sent a copy of our visa to them seeking their approval before we would be allowed to board the flight. We were then told that the representative had denied our boarding and we had to abandon our entire schedule.
Since we already have a visa, can we rearrange the entire booking to Italy (max days) and then smaller trips to Austria, Hungary, Czech, etc.
Should I be checking with the Italian embassy if at all there is an objection on the existing Schengen visa, considering the fact that the matter has already been reported to the Austrian border police representative.
I am traveling with my family and want to avoid any further issues now. I am willing to change our itinerary matching with the visa requirement of Italy with max days and first entry into Venice. However my exit would still be from an Austrian port. Will there be any issue?
If the visa hasn't been revoked or annulled, there is no reason you could not use it again. Landing in Italy, staying there the longest and generally following your original itinerary would be safest and if you do that, exiting through Austria is certainly not a problem.
If you are really concerned about the Austrian police, you could keep evidence of your stay in Italy (receipt from hotels, restaurants, or shops, train tickets, etc.) but once you are on your way out and as long as you did not violate the conditions (duration/validity) of your visa, they should care a lot less.
In fact, this arrangement with a “police representative” is a bit curious, it seems to me that the airline exceeded their authority as it seems you did have a valid visa. They certainly have to check that but can't possibly conduct a full border check themselves.
On the other hand, if you change your itinerary completely and present yourself to the border, you are in a bit of a grey area (see e.g. Should my first trip be to the country which issued my Schengen Visa?) and the Austrian police may very well choose to deny entry. In some cases, they can even cancel a visa so having a valid visa is certainly not a guarantee that you will be granted entry. But for all this, there are procedures to follow and you would have at least received a standard form with an explanation.
I am not a lawyer and have no idea whether that could be actionable but being effectively denied entry at the behest of the police without following the procedure or offering any justification seems to violate the spirit of the regulation, especially since the EUCJ ruled that the conditions listed in the Schengen Borders Code are the only ones that can justify being denied entry (point 69 in the judgment on case C‑575/12).
The good thing for you is that since, according to what you wrote, they did not in fact deny you entry, let alone cancel your visa, there is no denial stamp in your passport and your visa is still valid. There might be some record in some Austrian database but that should not have any consequence should you seek admission to Italy.
In any case, contacting the Italian embassy is certainly not a bad idea. Being upfront and proactive is the best and you would then have some tangible evidence that you are not trying to abuse the system (if you get an answer from the embassy, you could for example take a printout of the email with you).