There are multiple reasons for the German's myopia regarding Enigma and the consistent success of Anglo-American code-breaking efforts during the war. Firstly, the Third Reich partitioned out its cryptography and intelligence units into each military branch and civilian agencies. This fostered a degree of interservice rivalry for scarce resources and the lack of any central agency prevented any collective sharing of information. These intelligence branches at various points almost stumbled upon the Allies' efforts when investigating German losses, but because of their relative isolation of German intelligence, these investigations could never see the whole picture. There was little capability to pool and disseminate information even within the military. U-boat captains were increasingly apprehensive about Enigma's security as the Battle of the Atlantic dragged on, but there was no way for their concerns to filter to the appropriate channels. Therefore, much of the German investigations into signals breeches were reactive in nature, such as examining upticks in u-boat losses, in which the fog of war could always provide an alternative explanation to the fact that Enigma had been compromised.

But interservice rivalries and deficient investigations are only one part of the puzzle for Germany's collective failure. One problem that hampered the Germans was the military culture of the Wehrmacht that fostered a mentality that was ultimately counterproductive. The German military establishment did not place much stock into intelligence work as a proper military occupation, and thus its staff were seldom the cream of the crop. The military also looked only to the military for recruits for cryptanalysis and ciphers. This was in stark contrast to Bletchley Park, which recruited experts from outside military circles like members of the national bridge team or porcelain specialists whose hobbies and occupations trained them to see unusual patterns. The military's elitist cliquishness frequently looked down upon non-military personnel and was one of the main rationales behind the wide-scale adaptation of Enigma. The device represented a mechanization of ciphering and therefore could be trusted to trained conscripts. This snobbery came to fore when discussing Enigma as a source of Allied successes, one common explanation was that the device itself was being used improperly by a poorly trained operator. Nor was the relatively insular German academic establishment willing to cooperate with the military given there was a long-standing prejudice against practical application of their research. The military men in charge of Germany's efforts also tended not to conceive of wider applications of intelligence analysis. The Germans' decentralized intelligence networks also was geared to find immediate tactical information; using cryptography for strategic information was something that never quite occurred to them. The Wehrmacht's decentralization fostered a degree of hyperspecializtion that hindered its ability to shift focus.

Another handicap that hobbled the Germans was their past successes had inculcated a sense of complacency. Early war German efforts at breaking Allied cyphers cemented an opinion that the Allies' cryptography was sloppy and not run by professionals. When estimating their opposites, they frequently felt that while the British and Americans relied far too much upon technology, and not upon human capital. For the Germans, cryptanalysis was fundamentally a human occupation. Therefore they assumed that any attempt to break Enigma would rely upon human calculations (geistige Arbeit) and the mechanization of Enigma would preclude a brute force attack using human beings. Several times during the war, the Germans instituted precautionary attacks upon the Enigma messages in exercises and concluded that the machine could not be broken using German methods. Such a preconceived notion proved fatal for investigations into Enigma security because it fostered the tendency of the Germans to look for reasons other than Enigma to be the culprit. Some of this resulted in simple scapegoating such as considering the Italians' allegedly poor security to be the cause or some treason committed by German PoWs. Other times, the Germans considered Allied superiority in radar and radio-direction finding to be the culprit. Allied successes in cryptanalysis counterintuitively played a great role here as the speed at which Bletchley Park could decipher German messages and disseminate this intelligence was far faster than what the German intelligence establishment considered plausible.

Although the various German intelligence agencies bear a great deal of blame for large-scale systematic failures surrounding Enigma, it is also important to underscore their mistaken conclusions had some logical validity at the time. Allied radar and other material superiority was increasingly apparent as the war went on and many Germans did spy on the Third Reich for foreign powers. The Germans did try to use a Hollerith punch-card computer in 1943 to aid their cryptanalysis. The initial focus upon immediate tactical information makes some degree of sense for the quick and sudden type of war Germans wanted to fight. Even a more centralized intelligence establishment would not have resolved all of the material shortcomings and personnel problems given that such an agency would have still had to compete with other components of the Third Reich's war machine for scarce resources. Rectifying these problems was so vast it made the willful ignorance of Enigma's failure an attractive proposition.

Sources

Alvarez, David J. Allied and Axis Signals Intelligence in World War II. London: F. Cass, 1999.

Ratcliff, R. A. Delusions of Intelligence: Enigma, Ultra and the End of Secure Ciphers. Cambridge: Cambridge University Press, 2006.

There's a lot of conjecture in this question, so at the risk of putting myself out there; yes, your idea is fully possible.

Of all the weaknesses of the German military, intelligence gathering and security was probably among their greatest.

Did the Axis powers' incredulity have to do with how out of this world / fantastic to them was the notion that the Allies could have developed computing machines that could handle the large mathematics required to accomplish this?

No, not exactly. There's nothing particularly shocking about having found an algorithm or using some method of computation to do this. The shock-factor in breaking the Axis code came from the belief that it could be broken but that it would require an engima machine or other cipher machine to fall into Allied hands. They did, of course, but the Allies strained every nerve to hide the acquisition of an enigma machine from the Germans.

The rejection comes from the lack of evidence that an engima machine had been captured, and as a result quite a bit of complacency resulted. As a rule, when abandoning ship, Axis officers had to destroy the machine or scuttle the ship they were abandoning. In many cases, especially for U-Boats, they were able to do so in a timely manner. Even then, having the machine is only the first step in what the Germans believed would be a drawn-out process to crack the code. That is where the relative speed, courtesy of computation machines, comes into play.

and they couldn't bring themselves to imagine that the Allies had developed computers to solve these problems?

They could, though, there's evidence that they imagined the end, if not the means (which frankly are irrelevant). Its interesting to note that Allied intelligence, a titan compared to the blundering German counterpart, was blind in key instances. Intelligence was disastrously wrong or willfully ignorant, for example, about enemy forces in Holland prior to Op Market Garden. The Germans, suspecting a compromise, planned the Ardennes offensive using non-traditional means. In Normandy and other static fronts, wireless transmissions were avoided whenever possible. These are all signs that the Germans had an inkling late war that something was seriously compromised in their intelligence department; at the very least a marked improvement in their standard operational security.