Microsoft Support
I called them and they did provide the hotfix for free. Thanks.
I also fixed the problem by lowering th Max Memory option without any noticeable performance degradation. If the problem doesn't resurface, I probably won't install the patch. It isn't exactly straightforward to install or uninstall.
P.S. Fixing the query using a temp table was an option but somehow I think even for a complex query, SQL Server should be able to return more than 500 records.
Nick Duckstein
SQL Server DBA