Fey would seem to be a native English word. See Etymology On Line's entry. If it is common to the British Isles' Celtic languages it is probably because they got it from English. To say that they Brythonic languages predate Old English does not draw a good picture. The Goidelic (Irish and Scots Gaelic and Manx) and Brythonic (Welsh and Cornish) languages are in a completely different branch of the Indo-European languages from the Germanic group, of which English is an example.