The first video mentioned is the game MUSHIHIMESAMA FUTARI. I have not had a chance to try it because it cannot currently be dumped or played via emulation and Japanese shooters NEVER get sent to the US because arcades are dying out VERY rapidly. Japan is still producing arcade games and it is still a very strong industry there. Both Mushihimesama and Ikaruga are arcade shmups and would have never been created without the Japanese arcade culture. If you like Ikaruga you should also try the other big shmup by Treasure-Gradius V.
The Nintendo DS just got a port of Ketsui which is another bullet hell style game made by Cave, a well known and widely accepted shooting game company. The DS is region free so you can try the game on any system. The only problem is the 60 dollar price tag. The game is a light version of the arcade original. This port is lacking actual levels, it is rather what we call a "boss rush" game.
The funny thing is that the Japanese don't need to translate most of their shooters due to English menus. It seems like simple English is a cool novelty to them.
The hardest boss I've ever played would probably have to be something from a bullet hell game. I have played too many to nail down just one. Mushi's bosses are just plain coin eaters from what I can gather. Some people will agree that DoDonPachi Dai Ou Jou is also hell. However the whole point of a shooting game is to complete it in one credit not keep feeding coins into it. I don't say I've beaten one unless I've done it with the first credit even on console versions.
If you want to try these games you have some options.
If you are really dedicated you can modify your system to play Japanese games however be aware that some import shmup games are going for hundreds of dollars
used. If you have the money to invest your best bet is getting a Japanese system or modding yours. Also note that the European systems are completely different than the US and Japanese systems due to power and video differences. You cannot buy a Japanese system and plug it into a European outlet and television it will not work. However Americans and Japanese systems work on the same power and video.
Sega Saturn - region locked but does have DoDonPachi if you import or MOD
Dreamcast - Region free if you create a Utopia boot disk. A few bullet hell games.
PS2 - Mobile Light Force 2 + Castle Shikigami 2 in all regions, If you MOD chip there are MANY Japanese options.
XBOX - XBOX Live (Japanese) is getting a really great lineup
Wii - Has Castle Shikigami III and some older shooters via the Virtual console
PC - Also region free, there are many people who make "Doujin" games, which are hommade shooters and also there are a few professional ones too.
There are also ways to emulate fairly modern arcade shooters via PC but this forum will not discuss where or how to do that in compliance with copyright restrictions. There are plenty of freeware games too and I have posted a link some time ago in the links section. Also probably any decent coder here could make a shmup, about the easiest genre to make but hardest to balance.
Well Shockwave said that I would have something to offer.

All I'm saying is that bullet hell games probably have the most fair but difficult bosses. Oh and Mushi and Dai Ou Jou are just bullet spam to most people.