Spot the cat changed breeds about eight times from his first appearance to the last - I'm pretty sure in one TNG episode they stuffed up completely and he had kittens.

I figure he's a constantly mutating alien cat - the alternative explanation is too grim to ponder on. ("Captain, I have ascertained that cats do not have gills, and therefore can not breathe underwater.")