Can Malaysians enter North Korea without a visa? If the requirement changes anytime in the future, how can I re-verify at a later date (without calling my embassy, I mean)?
As of April 2017 holders of normal passports of all countries require a visa to visit North Korea. All visitors traveling for tourism require an authorization from a North Korean travel agency.
An exception exists for Chinese tourists visiting only the Tongnim County who can stay in this county instead Chinese ID card of a visa and passport for up to two days. They may also visit Sinuiju for a day trip without a visa and passport.
Additionally holders of diplomatic or service passports issued to nationals of the following countries can visit North Korea without a visa:
Given North Korea's position in international relations, this is unlikely to change anytime soon, but to get the latest information, you should ask a North Korean embassy or consulate, or other diplomatic representative. Only ask your own country's embassy if North Korean diplomatic representation is unreachable for some reason.
Please note, that Malaysia issued a travel ban for the DPRK in September 2017. Before that Malaysian passport holders were among the very few who could visit without a visa.
This doesn't necessarily mean you can't enter the country, just that you probably shouldn't. The DPRK doesn't stamp your passport but you'll get an exit and entry stamp from China or Russia. If you travel by train (for example via Dandong) this might (or might not) raise questions with Malaysia immigrations at some point because the exit stamps clearly indicate which country you're going to.
With some exceptions, travelling to the DPRK is only possible as part of an organized tour. You'll need to find an agency willing to take Malaysian citizens into the country (some refuse to take US citizens since a travel ban has been introduced for them). They will then take care of the visa process for you.
To answer your question, it's hard to figure out because the information available online isn't completely decisive and things have changed since the killing of Kim Jong-nam in Kuala Lumpur in February 2017. Before that, visa-free travel has been possible between these two countries. My suggestion is to contact a DPRK consulate or, possibly even better, one of the travel agencies specialising in the country. They should be able to give you up-to-date information on the exact rules.
Besides a DPRK visa you'll also need either a Chinese or a Russian one because as of today these are the only countries to enter North Korea from. There is 72-hour visa-free transit in some Chinese airports (including Beijing and Shanghai) but Malaysian passport holders don't qualify.
Note: I've visited the DPRK in 2011 and 2019.
Update: Koryo Tours, the longest-operating DPRK tour operator, updated their FAQs:
Those travelling on American and Malaysian passports are legally allowed to visit by the DPRK, but not by their own governments without special permission.
In general, I would trust their advice if you consider going. Contact them to clarify the latest situation.