I think the best fix would be to make nautilus scan files for the shebang AND have executable permissions before asking. The issue is atm files copied from NTFS partitions, etc. have all permissions enabled and so it asks for execution on every file, checking for the #! is much better behaviour IMO. Whether this is feasible or not I do not know, but you are only looking at scanning the first few characters of the file.
I think the best fix would be to make nautilus scan files for the shebang AND have executable permissions before asking. The issue is atm files copied from NTFS partitions, etc. have all permissions enabled and so it asks for execution on every file, checking for the #! is much better behaviour IMO. Whether this is feasible or not I do not know, but you are only looking at scanning the first few characters of the file.