If Puerto Rico is considered International, then it would be the Baxter team from Puerto Rico that started in 1997. If Puerto Rico isn't considereded international since it is a territory, then it would be Woburn (188) which started in 1998.
Off Kilter was the band that played in 1999. And they describe themselves as celtic, not scottish.
http://www.offkilter.net/index.html
I remember everyone talking about how cool the placebo was in 1997, but I never watched a match with it, and don't know.