An hypothetical island feigned by Shakespeare to be enchanted, and inhabited by witches and devils. Supposed by some to be Bermudas; but a correspondent in Notes and Queries (January 23rd, 1886, p. 72) utterly denies this, and favours the suggestion that the island meant was Lampedusa.
“From the still-vexed Bermoothes, there she's hid.”
Shakespeare: The Tempest, i. 2.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Bermoothes from Infoplease: