自然科学是一套理论体系。这套理论是我们用来描述现象的工具？还是“客观现实”的对应物？这个问题本身不是自然科学的问题 - 我们可以把它看做是科哲的问题。
派生出来，就有实在论（realism）的视角和反实在论（anti-realism）的视角。前者认为存在一个不依赖于主体的“实在”，科学理论应该是一种对实在的真实描述：科学理论的真假就体现在它与实在的对应性，它应该在一定范围内形成与“实在”的同构物。也就是说，科学的好坏在于其真假性。后者则认为超出主体的实在是无意义的，只有我们可观察的现象才有意义，那么科学理论应当是我们用来表述、预测我们能够观察到什么现象的工具，科学的好坏在于其有效性。
如果从实在论的视角看，那么逻辑本身的性质、尤其是认识论性质，就是一个很有意思的问题。从实在论看来，逻辑也是对实在的一种表述。而我们的理论总是在一步步向着“实在”收敛，那么逻辑也就不能独善其身。从蒯因的《两个教条》中已经有暗示，逻辑本身并不能免疫于经验检验。
@刘镇锐 的回答中提到，人们曾经试图修改排中律来满足量子逻辑（后来被编辑掉了？），这是真的。这种尝试出现在两篇同名论文之中，“Is Logic Empirical?”，作者分别是Putnam[1]和Dummett[2]。我本人还没有时间仔细阅读这些文献，所以这里都是从维基百科上搬运的东西。从维基上的寥寥数语，似乎第二篇论文更加有趣，它最终把这个问题归结为实在论与反实在论之争。
如果从反实在论的视角来看，那么在很多时候，科学理论的实用性其实会压倒其自洽性。所以历史上往往会出现一个无法解决的悖论（例如统计力学的反演诘难和复现诘难），严重威胁理论的自洽，但是人们在无法争论出子丑寅卯之前，一般会选择搁置它。这样一来，人们明知理论中有可能存在不自洽的地方，但是鉴于其实用、好用，人们仍然会用它，并且承认它的科学地位。
所以说，“自然科学完全遵循逻辑吗？”这个问题，答案是不一定。人们既有可能根据自然科学来修正逻辑，也有可能搁置科学理论中的悖论。从实在论角度，逻辑本身也是对现实的近似描述，随着理论的进化，它本身也在变化；而从反实在论的角度，逻辑就是我们制造出来的用于表达理论的formal工具，为了更好地表达，我们当然可以修改工具。
至于题主的另一个问题，把逻辑看做是“思维方式”。
“为什么人的思维方式能够较为有效地整理分