The 180W reasoning is wrong. You don't have the full 12V across the fuse, only a fraction of it. Say the fuse has a 0.1\$\Omega\$ resistance, then 15A will cause a power dissipation of
\$ P = I^2 \cdot R = (15A)^2 \cdot 0.1 \Omega = 22.5W \$.
And that 22.5W in the thin wire is just too much, and the fuse will blow.
Note that the 12V doesn't appear anywhere in this, and you could do the same calculation for 15A at 230V AC. There's a "but", however. Fuses do have a rated voltage. Not for the blowing, as we've seen, but to make sure the remains of the fuse won't cause sparks when at a high voltage. So you can't use a 12V car fuse in a mains appliance, but the other way around should be safe.
Automatic fuses also react on current only. They have a coil which releases a latch if the number of coil-windings exceeds the rated value. Also here it's independent of voltage.
I was an electrical engineer in the 1950s, part of my work was concerned with testing and selecting fuses. I recently gave a talk to my local amateur radio club on the subject, and what follows is from the script I wrote for that talk. I think it is relevant to the discussion here.
A surge protection fuse must accommodate three overload regions. For a short circuit it must blow fast in the normal way. It must also blow for steady overload currents just like an F fuse, but it must tolerate continual brief over-currents -- say ten times its rating -- without blowing or deteriorating.
Three main techniques are used to accomplish this. The simplest is to increase the thermal mass of the element, using a thicker, and therefore longer wire (to get sufficient resistance to heat up), wound round an insulating core, with careful control of the spacing for consistent operation. Pictures of this type and the next are in @Russell McMahon's answer. I have not seen an explanation of the fuse with the wavy wire.
The second technique employs a three part fusible element.The first part is a wire with a high melting point so that it will absorb surges, while still blowing fast on extreme overload. This is similar to an F fuse working at well below its rating, so it will not protect against overloads close to the rated current. The second part gets round this, providing the protection for currents that are closer to the rated value but not high enough to blow the thin wire itself, and consists of a lump of lower melting point material in series with
the main wire, that heats more slowly than the wire. The third part of the element is a stout spring of relatively high resistance material, helping to heat up the lump, and pulling it rapidly apart when it melts. The combination of lump and spring, with its relatively high thermal mass, also allows the surge to pass, but provides the protection for longer term but lesser overloads. There are many variations on this design and it gives manufacturers a lot of parameters for adjusting the fuse characteristics. Occasionally, as in the image above, a by-pass wire across the spring is used to adjust the characteristics of the fuse.
The third method employs the 'M' effect. In the 1930s Prof. A.W.Metcalf (hence the 'M') researched a phenomenon where the tin alloy used to solder the ends of the fuse seemed to affect the time to blow, reducing it in a strange way. He found that a spot (the 'M' spot) of solder on a silver wire element did not affect the short circuit performance, but it did reduce the time to blow on a sustained lower current. In this case, at the lower temperature of the wire, the solder diffused into and alloyed with the silver to create a region of high resistance in the spot, which would glow red hot, with the wire rupturing next to it. This, with suitably chosen alloys, nicely gives the characteristic needed for a surge resistant fuse. A problem with this type of fuse is that occasional currents just above the rated value may cause some unwanted diffusion to occur, altering the fuse characteristics without visible change.
Here is a picture of three M spot fuses, and yes there is a tiny spot on the top one.
Best Answer
Thanks to many commentators, I was finally able to blow my fuse.
The main point is, batteries have a significant internal resistance. Hence, they do not provide a "virtually unlimited current". Hence, there weren't enough current to blow the fuse initially.
As Respawned Fluff suggested, I have connected 3 AA batteries in parallel and connected them to the fuse. Connecting the batteries in parallel resulted in a lower total resistance while keeping the voltage the same at the same time, which in turn resulted in an increase in the current. Hence, this had produced sufficient current to fuse the fuse.