I think this is related to the Korean Wave in Japan.
In the early 2000s, Korean live action dramas and KPop started to come into Japan and quickly became massively popular. From Korea.net's article on the Korean Wave:
The Korean Wave landed in Japan in 2003 when the KBS TV drama series
Winter Sonata was aired via NHK. The drama became an instant mega hit,
making its male hero, Yon Sama, a household name, compelling his
enthusiastic Japanese fans to visit various film locations, including
Namiseom Island, in Korea.
In 2000, the K-Pop singer BoA took off her musical career with SM
Entertainment and two years later, her album Listen to My Heart became
the first album by a Korean musician to sell a million copies in Japan
on the basis of a Recording Industry Association of Japan page on million-selling records in 2002.
Korean media has gotten so popular in Japan that it's even prompted a backlash among some, as this article from The Atlantic notes.
The period of time when Inuyasha was on the air was squarely in the middle of the Korean Wave. I don't follow Naruto so I don't know exactly which years that particular song was used, but most of the Naruto anime's run has also been during peak years of the Korean Wave. Since BoA and Kara were already extremely popular in Japan, they were tapped to contribute songs for these anime, just as any other popular band would be. They were already touring and otherwise active in Japan, so I'm sure they had contacts that the anime studios could get in touch with to offer them these gigs.
To address the last point, there wasn't a shortage of Japanese bands; the studios just wanted to use these particular Korean bands because of their popularity. Using a foreign band isn't likely to be more expensive; it might even be cheaper, if the foreign band isn't well known, because they'll be willing to trade some pay for exposure. With these bands, since they were already popular and active in Japan, hiring them probably cost about what hiring an equally popular Japanese band would cost.