You could make it even easier to navigate by adding a map.
Instead of listing by embassies in a particular country, you should list by embassies of a country. To give you an example, if I'm thinking of going to France, I'm looking for the French embassy's website, not where I am applying from. That second bit of info is also needed, but you could ask that in the second filtering stage or by guessing the user's location.
I have tackled the embassies in vs embassies of on the listing and quite frankly, I don't have enough points of reference to make a call. There is a nifty search box on the right that allows you to filter though
A simple alternative I could think of is to get rid of the list of countries and make the search form on the right the main interface. You only need to ask "where are you going?", "where from?" and "your nationality". Simple search boxes or dropdown menus with flags would be great.
The widget will also take you to a service that will help fill out your visa application and deliver it. Their fees depend on the service you require.
I also constantly email all the embassies/consulates in the database for updated information because, and many people don't know this, embassies/consulates in smaller countries are usually the house where the ambassador lives. So when they change (and they often do), so does all the contact info.