I configured a new VirtualURI (regex).

class -> info.magnolia.cms.beans.config.RegexpVirtualURIMapping
fromURI -> /search/(.*)
toURI -> forward:/MyPage/de_DE/Search.html?q=$1

I tested the configuration several times with the following url:

www.foo.bar/search/ipod

It did not work (404).
After I found the problem (typo), I fixed the configuration, but it was not possible to access www.foo.bar/search/ipod anymore.

Slightly different URLs like www.foo.bar/search/ipod2 or www.foo.bar/search/iphone worked.

I restarted magnolia, problem persisted.
I assumed that the 404 would be cached by magnolia and deleted the cache directory and restarted again, then it worked.

From my point of view, 404's in VirtualURI mappings should not be cached (at least not forever) by magnolia.