这里要看上下文。按你的句子来理解，foreign可理解为“陌生的”“未知的”，相当于not known or familiar，这样用的 foreign 是可以有比较等级的。你的句子可理解为：

We could not have felt more foreign. 我们感到十分陌生。

这里要注意到另外一个语言点，那就是比较级与否定词连用，是表示强调，意思是指“没有比这更……”，也就是“最……”“十分……”“非常……”之类的意思。又如：

The staff couldn’t have been more helpful. 职员们十分愿意帮忙。

The two brothers could not have been more different. 兄弟俩的差别太大了。

Wilkins’ outburst could not have been more ill-timed. 威尔金斯脾气发作得实在太不是时候了。

Peter was a born leader, and his chairmanship of the WWF could not have been more effective. 彼得是个天生的领袖，他领导世界自然保护基金会非常有成效。