I have heard from card shops that Yu-gi-oh! is not worth getting into, because it is becoming to expensive. I just wanted to run the original Kiba deck, which i am very fond of, but i doubt it would hold up today. Does anyone have tips on how an old Yu-gi-oh! player can be relevant? Maybe even there is a card game out there that mimics the classic style?
Some people have old-school leagues at their local game shops where they play with older cards. If you don't have something like that in your vicinity, and you don't have any friends to play old-school Yugioh with, it's hard to recommend getting into it if you want to play old-school.
If you are also interested in normal, "modern" Yugioh, be aware that today's Yugioh plays a lot faster and is a lot more complicated (with tons of additional rules) than it was at the time when the original starter decks were released.
For the most part, the really expensive cards are those which are used in the most popular tournament decks. If you want to play a deck that is not used in the tournament scene, it's very possible that it is cheap to get.
As for your deck choice in your question: Besides having absolutely no chance of winning against even decks that would be considered "bad" today, the original Kaiba starter deck is also expensive as hell to get, because it's so old. I would recommend the newer Kaiba decks (e.g. the Kaiba structure deck) if you want Kaiba. Although those also have no chance against tournament decks, it can be played against the Yugi structure deck in a balanced way with friends.