It may be worth observing that "painfully slow" and "painstakingly slow" are by no means equally common in English. Here is a Google Ngram chart comparing "painstakingly slow" (blue line) to "painfully slow" (red line) for the period 1750–2005:
As the chart indicates, "painfully slow" has been in written use much longer and is considerably more common than "painstakingly slow." The earliest Google Books match for "painfully slow" is from "The Female Deserter," in A Lady, Poems, Moral & Entertaining (1808):
While the thoughtless, the happy, and gay,/Impatiently murmur at time,/And complain, his light wings brush away,/The blossoms of life in their prime;/The children of sorrow may grieve,/At a progress so painfully slow,/That it neither suspense will relieve,/Nor a respite from anguish bestow.
The poem is rather weak from beginning to end, but the writer's use of "painfully slow" is apt because she means "so slow as to be painful."
The earliest confirmed Google Books math for "painstakingly slow" is from Richard Parker, Claude de L'Estoile: Poet and Dramatist (1930) [combined snippets]:
The Intrigue des filous  was the last complete play which the poet [Claude de L'Estoile] wrote. His method of composition was painstakingly slow, as is evidenced by the small quantity of verse left by him.
The meaning of "painstakingly slow" here is unmistakably intended to be "slow as a result of painstaking carefulness"—which is entirely appropriate to the context. But other fairly early occurrences of "painstakingly slow" seem not to have that sense of the phrase in mind. For example, from Capital Transit Company, "Annual Report" (1954) [combined snippets]:
The private automobile is the competitor of public transit. This becomes more evident with each passing day. While no one desires to place limitations upon the operation of private automobiles, restrictions on promiscuous parking, particularly in the downtown area of Washington, are painstakingly slow in bringing about the recognition that public transit is "downtown's most gleaming diamond" which must be preserved and fostered.
And from Ron Schara, "Minnesota," in Field & Stream magazine (September 1971):
Pheasants are on a painstakingly slow comeback in the state. A May census of adult birds showed an 8-percent increase, and good nesting weather has prevailed. Last year hunters bagged some 150,000 cock birds and the harvest is expected to increase this fall, when the season opens. ... The southwest and western parts [of the state], normally top hunting grounds still are recovering from a severe winter that wiped out 50–90 percent of pheasants two years ago.
Neither recognition that public transit is crucial to the well-being of Downtown Washington, D.C., nor the comeback of pheasants in Minnesota following a harsh winter is slow as a result of painstaking carefulness. It follows that painstakingly is not a suitable word in either instance. Whether "painfully slow" would have been a better choice depends on whether the author meant that the process under discussion was "so slow as to be painful." If so, painfully works as a modifier; if not, perhaps not using any modifier before slow would have been better choice.
The poster is correct in noticing that "painstakingly slow" is sometimes used when "painfully slow" may be the intended meaning. On other occasions, however, it is used to mean exactly what you might expect it to mean: slow because of the painstaking effort involved.