Unfortunately, the government of Vietnam does not appear to host an (English) website listing all their official embassy sites. However, if your nation hosts a list of official missions, you may be able to find it there. Beyond that, searching for "Vietnamese Embassy " normally finds some viable candidates. Real embassy sites seem to always refer to "The Socialist Republic of Vietnam", and the front page will normally list announcements by Vietnamese officials, trade deals, etc.
In the case of Japan, it would appear all Visas are handled by the main embassy in Tokyo, hence your problems with the Osaka consulate. However, as the process seems to involve only posting off your passport, the exact location is unimportant. The process involves filling out a form, and sending, it, your passport, and the fee off together. See application page on the Vietnamese embassy site.
It is also possible to acquire a "Pre-approved Visa on Arrival" for Vietnam, provided your are entering by air to Ho Chi Minh, Hanoi or Da Nang airports. This tends to be cheaper than getting a visa through embassies, but has less flexibility and involves joining a queue at the airport. It also requires that the pre-approval is negotiated by a Vietnamese private agency. You can find a fairly detailed description fo the process in a TripAdvisor FAQ. Roughly speaking it works like this:
- Find a suitable agency, send the details they require and their fee off to them.
- The agency will send you a scan of a letter with your name (and possibly several others) on it, and an official Vietnamese government stamp.
- On arrival at the airport, you find the appropriate desk. You show your letter, hand over your passport, and pay another fee (the amount of this keeps changing and depends on your visa type), and the Visa is added to your passport. You can now proceed to immigration
Only limited types of visa are available on the pre-approved visa on arrival scheme. If you want another type of visa, or are arriving at a land border, sea border, or an airport not on the approved list, you will need a visa (or to be entitled to visa-free entry)