12v 25A 300x300 Heater bed Mosfet
I have looked over the 20 or so most expensive MOSFETs in that shop, and none are suitable.

It might be easier to go with a DC Solid State Relay rather than a bare MOSFET.

If you do want to go with a bare MOSFET instead, a TO-220 package MOSFET can dissipate around 1W without a heatsink, and around 3-4W with one. For 25A of current, that means the resistance of the MOSFET can be at most 1.6mΩ (without heatsink) or 5.6mΩ (with heatsink).

The IRLB3034 might be suitable. It is readily available on ebay (for under $1 shipped). 195A, 40V and an Rds(on) of only 1.4mΩ. A caveat is that this resistance is specified at a gate voltage of 10V, whereas it is slightly higher at lower gate voltages (1.6mΩ-2.0mΩ at 4.5V). This is on the upper edge of what is acceptable without a heatsink, but should still work (junction to ambient resistance is 62C/W, so in the worst case of 2.0mΩ the temperature would get to 77C above ambient - the MOSFET is rated for operation up to 175C). With a heatsink it will definitely work well.

Note that the gate charge is much higher (10x) than that of the MOSFET used on RAMPs so you should use a low switching frequency.