How did "riddled" come to be used as in the phrase "riddled with bullets"? Most definitions only include the puzzle type meaning.
"Riddled" in this meaning probably derives from the tool called a riddle, which is certainly riddled with holes:
According to Wiktionary, its etymology is:
From Middle English riddil, ridelle (“sieve”), from Old English hriddel (“sieve”), alteration of earlier hridder, hrīder, from Proto-Germanic *hridą (“sieve”), from Proto-Germanic *hrid- (“to shake”), from Proto-Indo-European *krey-.
As EL&U member 'rand al'thor' says, a 'riddle' is an old name for a sieve, and by extrapolation 'riddled' gained the meaning 'to put holes in something' (like a sieve). The Oxford English Dictionary suggests different origins for the word 'riddle' in the sense of a puzzle, and in the sense of sieved or punctured. Firstly, the puzzle sense:
Forms: α. 1 rǽd-, rédels, 4 redilis, 4–5 redel(e)s, 9 dial. ridless. β. 4, 6 redele, 4–5 redel, redil, 6 readle, redle, reedel, reedle. γ. 4–6 rydel, 6 ryddel(l, ryd(d)le, 4 ridil, 5 ridel, 6 riddel, ridelle, ridle, 6– riddle.
[OE. rǽdels masc. and rǽdelse fem., counsel, opinion, conjecture, etc., also a riddle, = Fris. riedsel, MDu. raetsel (Du. raadsel), OS. râdisli neut., râdislo masc. (MLG. râd-, rêdelse, rêdesal, LG. radsel), OHG. râdisle (MHG. ratsel, retsel, etc., G. rätsel), f. rǽdan to read or rede: see -els.]
- a. A question or statement intentionally worded in a dark or puzzling manner, and propounded in order that it may be guessed or answered, esp. as a form of pastime; an enigma; a dark saying.
Now, the OED on the sense of a sieve or something 'full of holes':
Forms: 1 hriddel, 4 riddil, 4, 6 riddill, 7 riddell, 6– riddle, 7, 9 dial. ruddle; 4 ridelle, 5 ridil, 6 redell, 7 ridle; 4 rydil, 5 ryddyll, rydyl, rydelle, 6 ryd(d)le.
[Late OE. hriddel: the earlier form is hridder ridder n.1]
- a. A coarse-meshed sieve, used for separating chaff from corn, sand from gravel, ashes from cinders, etc.; the most usual form has a circular wooden rim with a bottom formed of strong wires crossing each other at right-angles.
The OED mentions that an early version of the word for 'riddle' (in the sense of sieve) is 'ridder', and has this to say about that word:
▪ I.ˈridder, n.1dial.
Forms: 1 hrider, hridder 5 rydder, erron. rydoun, 7–9 dial. ridder, rudder, ruther.
[OE. hrider, later hridder, from a stem hrid- to shake (cf. hriðian to shake with fever), an ablaut-variant of which is represented by OHG. rîtera, rîtra (MHG. rîtere, rîter, G. reiter), and more remotely by L. crībrum, Ir. criathar. In later Eng. the more usual form is riddle n.2]
A sieve or riddle.
So two words in Old English, 'hrider' (to shake), and _'rǽdels' (counsel, opine or conjecture), lead to two words that are written and pronounced the same way, but have different meanings, 'riddle' (as in sieve), and 'riddle' as in puzzle.
What is interesting to note is that 'riddle' (as in puzzle) comes from an OE word that also led to the English word 'read', but as the OED suggests, the original meaning of that Old English word was actually 'counsel' or 'conjecture' (in the sense of 'puzzle out') , as explained here:
Pa. tense and pa. pple. read (red). Forms: inf. 1 rǽdan, (-on, ræddan, north. reda, reða), 3 ræden(n), raden, 2–4 reden, 5 redyn; (and pres.) 2, 4 rade, 3–6 rede, 5–6 reede, Sc. red, reid, 6 (8 Sc.) reed; (3) 6–7 reade, 6– read. (Also 3 sing. pres. 1 ræt, 2–4 ret, 3 red, 3–4 rat.) pa. tense 1 pl. reordun; 1 rǽdde, 3–4, 6 radde, (4 rade), 4, 6 rad, (4 rat); 1 pl. red(d)on, 3, 6 (9) redd, 4 redde, 4–6 rede, 4–6 (7–8) red, 7– read. pa. pple. 1 rǽden, 4 reddynn, 6 readen; 1 rǽded, 3–4 redd, 3–6 redde, (4 radde), 3–6 (7–8) red, 4 rede, 6 reed(e, 6– read; 1 ᵹeredd, 3 ired, 3–4 irad, 4 iredde, yrade, 4–5 iradde.
[Comm. Teut.: OE. rǽdan = OFris. rêda, OS. râdan (MLG. raden, MDu. and Du. raden), OHG. râtan (MHG. râten, G. raten, rathen), ON. ráða (Sw. råda, Da. raade), Goth. -rêdan:—OTeut. *ræ̂đan, prob. related to OIr. im-rádim to deliberate, consider, OSl. raditi to take thought, attend to, Skr. rādh- to succeed, accomplish, etc.
The Comm. Teut. verb belonged to the reduplicating ablaut-class, with pa. tense *rerōđ and pa. pple. *garæ̂đono-z, whence Goth. -rairôþ, *-rêdans, ON. réð, ráðinn, OHG. riat, girâtan (G. riet, geraten), OS. ried or rêd, *girâdan (Du. ried, geraden). The corresponding forms in OE. are reord and (ᵹe)rǽden, but these are found only in a few instances in Anglian texts, the usual conjugation being rǽdde, ᵹerǽd(e)d, on the analogy of weak verbs such as lǽdan: cf. MLG. radde, redde, Sw. rådde, and G. rathete (for usual riet), Da. raadede. The typical ME. forms are redde or radde in the pa. tense, and (i)red or (i)rad in the pa. pple.; in the later language (from the 17th c.) all tenses of the verb have the same spelling, read, though in pronunication the vowel of the preterite forms differs from that of the present and infinitive. Individual writers have from time to time denoted this by writing red or redd for the pa. tense and pa. pple., but the practice has never been widely adopted.
The original senses of the Teut. verb are those of taking or giving counsel, taking care or charge of a thing, having or exercising control over something, etc. These are also prominent in OE., and the sense of ‘advise’ still survives as an archaism, usually distinguished from the prevailing sense of the word by the retention of the older spelling rede. The sense of considering or explaining something obscure or mysterious is also common to the various languages, but the application of this to the interpretation of ordinary writing, and to the expression of this in speech, is confined to English and ON. (in the latter perhaps under Eng. influence).]
Having said all of that, the credit for the correct answer should go to EL&U member 'rand al'thor'.